Feedback arc set: Difference between revisions

From PsiForum
Jump to navigation Jump to search
m (Protected "Feedback arc set" ([Edit=Allow only administrators] (indefinite) [Move=Allow only administrators] (indefinite)))
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
−
{{good article}}
+
<!--Feedback arc set-->
−
{{Short description|Edges that hit all cycles in a graph}}
 
−
[[File:Feedback arc set.svg|thumb|Partition of a directed graph into a minimum feedback arc set (red dashed edges) and a maximum acyclic subgraph (blue solid edges)]]
 
−
In [[graph theory]] and [[graph algorithm]]s, a '''feedback arc set''' or '''feedback edge set''' in a [[directed graph]] is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing a [[directed acyclic graph]], an '''acyclic subgraph''' of the given graph. The feedback arc set with the fewest possible edges is the '''minimum feedback arc set''' and its removal leaves the '''maximum acyclic subgraph'''; weighted versions of these [[optimization problem]]s are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.
 
−
 
 
−
Feedback arc sets have applications in circuit analysis, [[chemical engineering]], [[deadlock]] resolution, [[ranked voting]], ranking competitors in sporting events, [[mathematical psychology]], [[ethology]], and [[graph drawing]]. Finding minimum feedback arc sets and maximum acyclic subgraphs is [[NP-hard]]; it can be solved exactly in [[exponential time]], or in [[fixed-parameter tractable]] time. In [[polynomial time]], the minimum feedback arc set can be approximated to within a polylogarithmic [[approximation ratio]], and maximum acyclic subgraphs can be approximated to within a constant factor. Both are hard to approximate closer than some constant factor, an [[inapproximability]] result that can be strengthened under the [[unique games conjecture]]. For [[tournament graph]]s, the minimum feedback arc set can be approximated more accurately, and for [[planar graph]]s both problems can be solved exactly in polynomial time.
 
−
 
 
−
A closely related problem, the [[feedback vertex set]], is a set of vertices containing at least one vertex from every cycle in a directed or undirected graph. In [[undirected graph]]s, the [[spanning tree]]s are the largest acyclic subgraphs, and the number of edges removed in forming a spanning tree is the [[circuit rank]].
 
−
 
 
−
==Applications==
 
−
[[File:Min-upset ranking MBV 2016 Pool F.svg|thumb|The scores from [[Beach volleyball at the 2016 Summer Olympics – Men's tournament|men's beach volleyball at the 2016 Olympics]], pool F, and the minimum-upset ranking for these scores. Arrows are directed from the loser to the winner of each match, and are colored blue when the outcome is consistent with the ranking and red for an upset, an outcome inconsistent with the ranking. With this ranking, only one match is an upset, the one in which USA beat QAT. The actual ranking used in the Olympics differed by placing ESP ahead of QAT on set ratio, causing their match to be ranked as another upset.{{r|fivb}}]]
 
−
Several problems involving finding rankings or orderings can be solved by finding a feedback arc set on a [[tournament graph]], a directed graph with one edge between each pair of vertices. Reversing the edges of the feedback arc set produces a [[directed acyclic graph]] whose unique [[topological sorting|topological order]] can be used as the desired ranking. Applications of this method include the following:
 
−
*In sporting competitions with [[round-robin tournament|round-robin play]], the outcomes of each game can be recorded by directing an edge from the loser to the winner of each game. Finding a minimum feedback arc set in the resulting graph, reversing its edges, and topological ordering, produces a ranking on all of the competitors. Among all of the different ways of choosing a ranking, it minimizes the total number of upsets, games in which a lower-ranked competitor beat a higher-ranked competitor.{{r|hubert|rt66|goddard}} Many sports use simpler methods for [[group tournament ranking system]]s based on points awarded for each game;{{r|vdym}} these methods can provide a constant approximation to the minimum-upset ranking.{{r|cfr}}
 
−
*In [[primatology]] and more generally in [[ethology]], [[dominance hierarchy|dominance hierarchies]] are often determined by searching for an ordering with the fewest reversals in observed dominance behavior, another form of the minimum feedback arc set problem.{{r|seyfarth|drafthorse|cockroach}}
 
−
*In [[mathematical psychology]], it is of interest to determine subjects' rankings of sets of objects according to a given criterion, such as their preference or their perception of size, based on pairwise comparisons between all pairs of objects. The minimum feedback arc set in a tournament graph provides a ranking that disagrees with as few pairwise outcomes as possible.{{r|hubert|slater}} Alternatively, if these comparisons result in independent probabilities for each pairwise ordering, then the [[maximum likelihood estimation]] of the overall ranking can be obtained by converting these probabilities into [[Likelihood function|log-likelihoods]] and finding a minimum-weight feedback arc set in the resulting tournament.{{r|hubert|rt66}}
 
−
*The same maximum-likelihood ordering can be used for [[Seriation (statistics)|seriation]], the problem in [[statistics]] and [[exploratory data analysis]] of arranging elements into a linear ordering, in cases where data is available that provides pairwise comparisons between the elements.{{r|rt66|brunk|rt64}}
 
−
*In [[ranked voting]], the [[Kemeny–Young method]] can be described as seeking an ordering that minimizes the sum, over pairs of candidates, of the number of voters who prefer the opposite ordering for that pair.{{r|kemeny}} This can be formulated and solved as a minimum-weight feedback arc set problem, in which the vertices represent candidates, edges are directed to represent the winner of each head-to-head contest, and the cost of each edge represents the number of voters who would be made unhappy by giving a higher ranking to the head-to-head loser.{{r|KarpinskiSchudy}}
 
−
 
 
−
Another early application of feedback arc sets concerned the design of [[sequential logic]] circuits, in which signals can propagate in cycles through the circuit instead of always progressing from inputs to outputs. In such circuits, a minimum feedback arc set characterizes the number of points at which amplification is necessary to allow the signals to propagate without loss of information.{{r|unger}} In [[synchronous circuit]]s made from asynchronous components, synchronization can be achieved by placing clocked gates on the edges of a feedback arc set.{{r|clock}} Additionally, cutting a circuit on a feedback arc a set reduces the remaining circuit to [[combinational logic]], simplifying its analysis, and the size of the feedback arc set controls how much additional analysis is needed to understand the behavior of the circuit across the cut.{{r|unger}} Similarly, in [[process flowsheeting]] in [[chemical engineering]], breaking edges of a [[process flow diagram]] on a feedback arc set, and guessing or trying all possibilities for the values on those edges, allows the rest of the process to be analyzed in a systematic way because of its acyclicity. In this application, the idea of breaking edges in this way is called "tearing".{{r|rh68}}
 
−
 
 
−
In [[layered graph drawing]], the vertices of a given directed graph are partitioned into an ordered sequence of subsets (the layers of the drawing), and each subset is placed along a horizontal line of this drawing, with the edges extending upwards and downwards between these layers. In this type of drawing, it is desirable for most or all of the edges to be oriented consistently downwards, rather than mixing upwards and downwards edges, in order for the reachability relations in the drawing to be more visually apparent. This is achieved by finding a minimum or minimal feedback arc set, reversing the edges in that set, and then choosing the partition into layers in a way that is consistent with a topological order of the resulting acyclic graph.{{r|dett98|bm01}} Feedback arc sets have also been used for a different subproblem of layered graph drawing, the ordering of vertices within consecutive pairs of layers.{{r|df01}}
 
−
 
 
−
In [[deadlock]] resolution in [[operating system]]s, the problem of removing the smallest number of dependencies to break a deadlock can be modeled as one of finding a minimum feedback arc set.{{r|enss|minoura}} However, because of the computational difficulty of finding this set, and the need for speed within operating system components, heuristics rather than exact algorithms are often used in this application.{{r|minoura}}
 
−
 
 
−
==Algorithms==
 
−
===Equivalences===
 
−
The minimum feedback arc set and maximum acyclic subgraph are equivalent for the purposes of exact optimization, as one is the [[complement set]] of the other. However, for parameterized complexity and approximation, they differ, because the analysis used for those kinds of algorithms depends on the size of the solution and not just on the size of the input graph, and the minimum feedback arc set and maximum acyclic subgraph have different sizes from each other.{{r|missik}}
 
−
 
 
−
A feedback arc set of a given graph <math>G</math> is the same as a [[feedback vertex set]] of a directed [[line graph]] {{nowrap|of <math>G</math>.}} Here, a feedback vertex set is defined analogously to a feedback arc set, as a subset of the vertices of the graph whose deletion would eliminate all cycles. The line graph of a directed graph <math>G</math> has a vertex for each edge {{nowrap|of <math>G</math>,}} and an edge for each two-edge path {{nowrap|in <math>G</math>.}} In the other direction, the minimum feedback vertex set of a given graph <math>G</math> can be obtained from the solution to a minimum feedback arc set problem on a graph obtained by splitting every vertex of <math>G</math> into two vertices, one for incoming edges and one for outgoing edges. These transformations allow exact algorithms for feedback arc sets and for feedback vertex sets to be converted into each other, with an appropriate translation of their complexity bounds. However, this transformation does not preserve approximation quality for the maximum acyclic subgraph problem.{{r|enss|Hecht}}
 
−
 
 
−
[[File:Scc-1.svg|thumb|upright=1.35|A directed graph with three [[strongly connected component]]s, the rightmost of which can be split at articulation vertex <math>d</math> into two [[biconnected component]]s, each a cycle of two vertices. The feedback arc set problem can be solved separately in each strongly connected component, and in each biconnected component of a strongly connected component.]]
 
−
In both exact and approximate solutions to the feedback arc set problem, it is sufficient to solve separately each [[strongly connected component]] of the given graph, and to break these strongly connected components down even farther to their [[biconnected component]]s by splitting them at articulation vertices. The choice of solution within any one of these subproblems does not affect the others, and the edges that do not appear in any of these components are useless for inclusion in the feedback arc set.{{r|pa92}} When one of these components can be separated into two disconnected subgraphs by removing two vertices, a more complicated decomposition applies, allowing the problem to be split into subproblems derived from the [[SPQR tree|triconnected components]] of its strongly connected components.{{r|np00}}
 
−
 
 
−
===Exact===
 
−
One way to find the minimum feedback arc set is to search for an ordering of the vertices such that as few edges as possible are directed from later vertices to earlier vertices in the ordering.{{r|younger}} Searching all [[permutation]]s of an {{nowrap|<math>n</math>-vertex}} graph would take {{nowrap|time <math>O(n!)</math>,}} but a [[dynamic programming]] method based on the [[Held–Karp algorithm]] can find the optimal permutation in {{nowrap|time <math>O(n2^n)</math>,}} also using an exponential amount of space.{{r|lawler|bfkkt}} A [[divide-and-conquer algorithm]] that tests all partitions of the vertices into two equal subsets and recurses within each subset can solve the problem in {{nowrap|time <math>O(4^n/\sqrt{n})</math>,}} using [[polynomial space]].{{r|bfkkt}}
 
−
 
 
−
In [[parameterized complexity]], the time for algorithms is measured not just in terms of the size of the input graph, but also in terms of a separate parameter of the graph. In particular, for the minimum feedback arc set problem, the so-called ''natural parameter'' is the size of the minimum feedback arc set. On graphs with <math>n</math> vertices, with natural {{nowrap|parameter <math>k</math>,}} the feedback arc set problem can be solved in {{nowrap|time <math>O(n^44^kk^3k!)</math>,}} by transforming it into an equivalent feedback vertex set problem and applying a parameterized feedback vertex set algorithm. Because the exponent of <math>n</math> in this algorithm is the {{nowrap|constant <math>4</math>,}} independent {{nowrap|of <math>k</math>,}} this algorithm is said to be fixed-parameter tractable.{{r|cllor}}
 
−
 
 
−
Other parameters than the natural parameter have also been studied. A fixed-parameter tractable algorithm using dynamic programming can find minimum feedback arc sets in {{nowrap|time <math>O(2^r m^4\log m)</math>,}} where <math>r</math> is the [[circuit rank]] of the underlying undirected graph. The circuit rank is an undirected analogue of the feedback arc set, the minimum number of edges that need to be removed from a graph to reduce it to a [[spanning tree]]; it is much easier to compute than the minimum feedback arc set.{{r|Hecht}} For graphs of {{nowrap|[[treewidth]] <math>t</math>,}} dynamic programming on a tree decomposition of the graph can find the minimum feedback arc set in time polynomial in the graph size and exponential {{nowrap|in <math>O(t\log t)</math>.}} Under the [[exponential time hypothesis]], no better dependence on <math>t</math> is possible.{{r|bknpsw}}
 
−
 
 
−
Instead of minimizing the size of the feedback arc set, researchers have also looked at minimizing the maximum number of edges removed from any vertex. This variation of the problem can be solved in [[linear time]].{{r|ls89}} All minimal feedback arc sets can be listed by an algorithm with [[polynomial delay]] per set.{{r|ss02}}
 
−
 
 
−
===Approximate===
 
−
{{unsolved|mathematics|Does the feedback arc set problem have an [[approximation algorithm]] with a constant approximation ratio?}}
 
−
The best known polynomial-time approximation algorithm for the feedback arc set has the non-constant [[approximation ratio]] {{nowrap|<math>O(\log n\log\log n)</math>.}} This means that the size of the feedback arc set that it finds is at most this factor larger than the optimum.{{r|enss}} Determining whether feedback arc set has a constant-ratio approximation algorithm, or whether a non-constant ratio is necessary, remains an open problem.{{r|compendium}}
 
−
 
 
−
The maximum acyclic subgraph problem has an easy approximation algorithm that achieves an approximation ratio {{nowrap|of <math>\tfrac12</math>:}}
 
−
*Fix an arbitrary ordering of the vertices
 
−
*Partition the edges into two acyclic subgraphs, one consisting of the edges directed consistently with the ordering, and the other consisting of edges directed oppositely to the ordering.
 
−
*Return the larger of the two subgraphs.
 
−
 
 
−
This can be improved by using a [[greedy algorithm]] to choose the ordering. This algorithm finds and deletes a vertex whose numbers of incoming and outgoing edges are as far apart as possible, recursively orders the remaining graph, and then places the deleted vertex at one end of the resulting order. For graphs with <math>m</math> edges and <math>n</math> vertices, this produces an acyclic subgraph with <math>m/2+n/6</math> edges, in linear time, giving an approximation ratio {{nowrap|of <math>\tfrac12+\Omega(n/m)</math>.{{r|els}}}} Another, more complicated, polynomial time approximation algorithm applies to graphs with maximum {{nowrap|degree <math>\Delta</math>,}} and finds an acyclic subgraph with <math>m/2+\Omega(m/\sqrt{\Delta})</math> edges, giving an approximation ratio of the {{nowrap|form <math>\tfrac12+\Omega(1/\sqrt{\Delta})</math>.{{r|bs97|hr94}}}} When <math>\Delta=3</math>, the approximation ratio <math>8/9</math> can be achieved.{{r|newman}}
 
−
 
 
−
===Restricted inputs===
 
−
In directed [[planar graph]]s, the feedback arc set problem is [[dual graph|dual]] to the problem of contracting a set of edges to make the resulting graph [[strongly connected graph|strongly connected]].{{r|gab95}} This dual problem is polynomially solvable,{{r|frank}}  and therefore the planar minimum feedback arc set problem is as well.{{r|ly78|frank}} It can be solved in {{nowrap|time <math>O(n^{5/2}\log n)</math>.{{r|gab93}}}} A weighted version of the problem can be solved in {{nowrap|time <math>O(n^3)</math>,{{r|gab95}}}} or when the weights are positive integers that are at most a {{nowrap|number <math>N</math>,}} in {{nowrap|time <math>O(n^{5/2}\log nN)</math>.{{r|gab93}}}} These planar algorithms can be extended to the graphs that do not have the [[utility graph]] <math>K_{3,3}</math> as a [[graph minor]], using the fact that the triconnected components of these graphs are either planar or of bounded size.{{r|np00}} Planar graphs have also been generalized in a different way to a class of directed graphs called ''weakly acyclic digraphs'', defined by the [[integral polytope|integrality]] of a certain [[polyhedral combinatorics|polytope associated with their feedback arc sets]]. Every planar directed graph is weakly acyclic in this sense, and the feedback arc set problem can be solved in polynomial time for all weakly acyclic digraphs.{{r|gjr85}}
 
−
 
 
−
The [[Control-flow graph#Reducibility|reducible flow graphs]] are another class of directed graphs on which the feedback arc set problem may be solved in polynomial time. These graphs describe the flow of control in structured programs for many programming languages. Although structured programs often produce planar directed flow graphs, the definition of reducibility does not require the graph to be planar.{{r|ramachandran}}
 
−
 
 
−
When the minimum feedback arc set problem is restricted to [[tournament (graph theory)|tournaments]], it has a [[polynomial-time approximation scheme]], which generalizes to a weighted version of the problem.{{r|MathieuSchudy}} A subexponential parameterized algorithm for weighted feedback arc sets on tournaments is also known.{{r|KarpinskiSchudy}} The maximum acyclic subgraph problem for [[dense graph]]s also has a polynomial-time approximation scheme. Its main ideas are to apply [[randomized rounding]] to a [[linear programming relaxation]] of the problem, and to [[Derandomization|derandomize]] the resulting algorithm using walks on [[expander graph]]s.{{r|compendium|afk02}}
 
−
 
 
−
==Hardness==
 
−
===NP-hardness===
 
−
[[File:Feedback arc set NP-completeness.svg|thumb|upright=1.35|The [[Reduction (complexity)|NP-completeness reduction]] of Karp and Lawler, from vertex cover of the large yellow graph to minimum feedback arc set in the small blue graph, expands each yellow vertex into two adjacent blue graph vertices, and each undirected yellow edge into two opposite directed edges. The minimum vertex cover (upper left and lower right yellow vertices) corresponds to the red minimum feedback arc set.]]
 
−
In order to apply the theory of [[NP-completeness]] to the minimum feedback arc set, it is necessary to modify the problem from being an optimization problem (how few edges can be removed to break all cycles) to an equivalent [[decision version]], with a yes or no answer (is it possible to remove <math>k</math> edges). Thus, the decision version of the feedback arc set problem takes as input both a directed graph and a {{nowrap|number <math>k</math>.}} It asks whether all cycles can be broken by removing at most <math>k</math> edges, or equivalently whether there is an acyclic subgraph with at least <math>|E(G)|-k</math> edges. This problem is [[NP-complete]], implying that neither it nor the optimization problem are expected to have polynomial time algorithms. It was one of [[Richard M. Karp]]'s original set of [[Karp's 21 NP-complete problems|21 NP-complete problems]]; its NP-completeness was proved by Karp and [[Eugene Lawler]] by showing that inputs for another hard problem, the [[vertex cover problem]], could be transformed ("reduced") into equivalent inputs to the feedback arc set decision problem.{{r|karp|gj79}}
 
−
 
 
−
Some NP-complete problems can become easier when their inputs are restricted to special cases. But for the most important special case of the feedback arc set problem, the case of tournaments, the problem remains NP-complete.{{r|alon|cty}}
 
−
 
 
−
===Inapproximability===
 
−
The complexity class [[APX]] is defined as consisting of optimization problems that have a polynomial time approximation algorithm that achieves a constant [[approximation ratio]]. Although such approximations are not known for the feedback arc set problem, the problem is known to be [[APX-hard]], meaning that accurate approximations for it could be used to achieve similarly accurate approximations for all other problems in APX. As a consequence of its hardness proof, unless [[P = NP]], it has no polynomial time approximation ratio better than 1.3606. This is the same threshold for hardness of approximation that is known for vertex cover, and the proof uses the Karp–Lawler [[reduction (complexity)|reduction]] from vertex cover to feedback arc set, which preserves the quality of approximations.{{r|compendium|adp80|kann|ds05}} By a different reduction, the maximum acyclic subgraph problem is also APX-hard, and NP-hard to approximate to within a factor of 65/66 of optimal.{{r|newman}}
 
−
 
 
−
The hardness of approximation of these problems has also been studied under unproven [[computational hardness assumption]]s that are standard in computational complexity theory but stronger than P ≠ NP. If the [[unique games conjecture]] is true, then the minimum feedback arc set problem is hard to approximate in polynomial time to within any constant factor, and the maximum feedback arc set problem is hard to approximate to within a factor {{nowrap|of <math>\tfrac12+\varepsilon</math>,}} for {{nowrap|every <math>\varepsilon>0</math>.{{r|ghmrc}}}} Beyond polynomial time for approximation algorithms, if the [[exponential time hypothesis]] is true, then for every <math>\varepsilon>0</math> the minimum feedback arc set does not have an approximation within a factor <math>\tfrac76-\varepsilon</math> that can be computed in the subexponential time bound {{nowrap|<math>O(2^{n^{1-\varepsilon}})</math>.{{r|bp18}}}}
 
−
 
 
−
==Theory==
 
−
In planar directed graphs, the feedback arc set problem obeys a [[min-max theorem]]: the minimum size of a feedback arc set equals the maximum number of edge-disjoint directed cycles that can be found in the graph.{{r|ly78|lovasz}} This is not true for some other graphs; for instance the first illustration shows a directed version of the non-planar graph <math>K_{3,3}</math> in which the minimum size of a feedback arc set is two, while the maximum number of edge-disjoint directed cycles is only one.
 
−
 
 
−
Every tournament graph has a [[Hamiltonian path]], and the Hamiltonian paths correspond one-for-one with minimal feedback arc sets, disjoint from the corresponding path. The Hamiltonian path for a feedback arc set is found by reversing its arcs and finding a topological order of the resulting acyclic tournament. Every consecutive pair of the order must be disjoint from the feedback arc sets, because otherwise one could find a smaller feedback arc set by reversing that pair. Therefore, this ordering gives a path through arcs of the original tournament, covering all vertices. Conversely, from any Hamiltonian path, the set of edges that connect later vertices in the path to earlier ones forms a feedback arc set. It is minimal, because each of its edges belongs to a cycle with the Hamiltonian path edges that is disjoint from all other such cycles.{{r|bn90}} In a tournament, it may be the case that the minimum feedback arc set and maximum acyclic subgraph are both close to half the edges. More precisely, every tournament graph has a feedback arc set of size {{nowrap|<math>\tbinom{n}{2}/2-\Omega(n^{3/2})</math>,}} and some tournaments require size {{nowrap|<math>\tbinom{n}{2}/2-O(n^{3/2})</math>.{{r|spencer}}}} For [[almost all]] tournaments, the size is at least {{nowrap|<math>\tbinom{n}{2}/2 - 1.73n^{3/2}</math>.{{r|fdlv}}}} Every [[directed acyclic graph]] <math>D</math> can be embedded as a subgraph of a larger tournament graph, in such a way that <math>D</math> is the unique minimum feedback arc set of the tournament. The size of this tournament has been defined as the "reversing number" {{nowrap|of <math>D</math>,}} and among directed acyclic graphs with the same number of vertices it is largest when <math>D</math> is itself an (acyclic) tournament.{{r|bhirt|in04}}
 
−
 
 
−
A directed graph has an [[Euler tour]] whenever it is [[strongly connected]] and each vertex has equal numbers of incoming and outgoing edges. For such a graph, with <math>m</math> edges and <math>n</math> vertices, the size of a minimum feedback arc set is always at least {{nowrap|<math>(m^2+mn)/2n^2</math>.}} There are infinitely many Eulerian directed graphs for which this bound is tight.{{r|hmssy}} If a directed graph has <math>n</math> vertices, with at most three edges per vertex, then it has a feedback arc set of at most <math>n/3</math> edges, and some graphs require this many. If a directed graph has <math>m</math> edges, with at most four edges per vertex, then it has a feedback arc set of at most <math>m/3</math> edges, and some graphs require this many.{{r|hba}}
 
−
 
 
−
==References==
 
−
{{reflist|refs=
 
−
 
 
−
<ref name=adp80>{{citation
 
−
| last1 = Ausiello | first1 = G. | author1-link = Giorgio Ausiello
 
−
| last2 = D'Atri | first2 = A.
 
−
| last3 = Protasi | first3 = M.
 
−
| doi = 10.1016/0022-0000(80)90046-X | doi-access = free
 
−
| issue = 1
 
−
| journal = [[Journal of Computer and System Sciences]]
 
−
| mr = 589808
 
−
| pages = 136–153
 
−
| title = Structure preserving reductions among convex optimization problems
 
−
| volume = 21
 
−
| year = 1980}}</ref>
 
−
 
 
−
<ref name=afk02>{{citation
 
−
| last1 = Arora
 
−
| first1 = Sanjeev
 
−
| author1-link = Sanjeev Arora
 
−
| last2 = Frieze
 
−
| first2 = Alan
 
−
| author2-link = Alan M. Frieze
 
−
| last3 = Kaplan
 
−
| first3 = Haim
 
−
| doi = 10.1007/s101070100271
 
−
| issue = 1
 
−
| journal = [[Mathematical Programming]]
 
−
| mr = 1892295
 
−
| pages = 1–36
 
−
| title = A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
 
−
| url = https://www.cs.princeton.edu/~arora/pubs/assign.ps
 
−
| volume = 92
 
−
| year = 2002
 
−
| s2cid = 3207086
 
−
| access-date = 2021-08-03
 
−
| archive-date = 2021-08-03
 
−
| archive-url = https://web.archive.org/web/20210803195618/https://www.cs.princeton.edu/~arora/pubs/assign.ps
 
−
| url-status = live
 
−
}}</ref>
 
−
 
 
−
<ref name=alon>{{citation
 
−
| last = Alon | first = Noga | author-link = Noga Alon
 
−
| doi = 10.1137/050623905
 
−
| issue = 1
 
−
| journal = [[SIAM Journal on Discrete Mathematics]]
 
−
| mr = 2257251
 
−
| pages = 137–142
 
−
| title = Ranking tournaments
 
−
| volume = 20
 
−
| year = 2006}}</ref>
 
−
 
 
−
<ref name=bfkkt>{{citation
 
−
| last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender
 
−
| last2 = Fomin | first2 = Fedor V.
 
−
| last3 = Koster | first3 = Arie M. C. A.
 
−
| last4 = Kratsch | first4 = Dieter
 
−
| last5 = Thilikos | first5 = Dimitrios M.
 
−
| doi = 10.1007/s00224-011-9312-0
 
−
| issue = 3
 
−
| journal = Theory of Computing Systems
 
−
| mr = 2885638
 
−
| pages = 420–432
 
−
| title = A note on exact algorithms for vertex ordering problems on graphs
 
−
| volume = 50
 
−
| year = 2012| hdl = 1956/4556
 
−
| s2cid = 9967521 | hdl-access = free
 
−
}}</ref>
 
−
 
 
−
<ref name=bhirt>{{citation
 
−
| last1 = Barthélémy | first1 = Jean-Pierre
 
−
| last2 = Hudry | first2 = Olivier
 
−
| last3 = Isaak | first3 = Garth
 
−
| last4 = Roberts | first4 = Fred S. | author4-link = Fred S. Roberts
 
−
| last5 = Tesman | first5 = Barry
 
−
| doi = 10.1016/0166-218X(94)00042-C
 
−
| issue = 1–3
 
−
| journal = [[Discrete Applied Mathematics]]
 
−
| mr = 1339075
 
−
| pages = 39–76
 
−
| title = The reversing number of a digraph
 
−
| volume = 60
 
−
| year = 1995| doi-access = free
 
−
}}</ref>
 
−
 
 
−
<ref name=bknpsw>{{citation
 
−
| last1 = Bonamy | first1 = Marthe
 
−
| last2 = Kowalik | first2 = Lukasz
 
−
| last3 = Nederlof | first3 = Jesper
 
−
| last4 = Pilipczuk | first4 = Michal
 
−
| last5 = Socala | first5 = Arkadiusz
 
−
| last6 = Wrochna | first6 = Marcin
 
−
| editor1-last = Brandstädt | editor1-first = Andreas
 
−
| editor2-last = Köhler | editor2-first = Ekkehard
 
−
| editor3-last = Meer | editor3-first = Klaus
 
−
| arxiv = 1707.01470
 
−
| contribution = On directed feedback vertex set parameterized by treewidth
 
−
| doi = 10.1007/978-3-030-00256-5_6
 
−
| pages = 65–78
 
−
| publisher = Springer
 
−
| series = Lecture Notes in Computer Science
 
−
| title = Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings
 
−
| volume = 11159
 
−
| year = 2018| s2cid = 8008855
 
−
}}</ref>
 
−
 
 
−
<ref name=bm01>{{citation
 
−
| last1 = Bastert | first1 = Oliver
 
−
| last2 = Matuszewski | first2 = Christian
 
−
| editor1-last = Kaufmann | editor1-first = Michael
 
−
| editor2-last = Wagner | editor2-first = Dorothea | editor2-link = Dorothea Wagner
 
−
| contribution = Layered drawings of digraphs
 
−
| doi = 10.1007/3-540-44969-8_5
 
−
| pages = 87–120
 
−
| publisher = Springer-Verlag
 
−
| series = Lecture Notes in Computer Science
 
−
| title = Drawing Graphs: Methods and Models
 
−
| volume = 2025
 
−
| year = 2001}}</ref>
 
−
 
 
−
<ref name=bn90>{{citation
 
−
| last1 = Bar-Noy | first1 = Amotz
 
−
| last2 = Naor | first2 = Joseph | author2-link = Joseph Seffi Naor
 
−
| doi = 10.1137/0403002
 
−
| issue = 1
 
−
| journal = [[SIAM Journal on Discrete Mathematics]]
 
−
| mr = 1033709
 
−
| pages = 7–20
 
−
| title = Sorting, minimal feedback sets, and Hamilton paths in tournaments
 
−
| volume = 3
 
−
| year = 1990}}</ref>
 
−
 
 
−
<ref name=bp18>{{citation
 
−
| last1 = Bonnet | first1 = Édouard
 
−
| last2 = Paschos | first2 = Vangelis Th.
 
−
| doi = 10.1007/s00236-016-0281-2
 
−
| issue = 1
 
−
| journal = Acta Informatica
 
−
| mr = 3757549
 
−
| pages = 1–15
 
−
| title = Sparsification and subexponential approximation
 
−
| volume = 55
 
−
| year = 2018| s2cid = 3136275
 
−
}}</ref>
 
−
 
 
−
<ref name=brunk>{{citation
 
−
| last = Brunk | first = H. D.
 
−
| doi = 10.2307/2281911
 
−
| journal = [[Journal of the American Statistical Association]]
 
−
| jstor = 2281911
 
−
| mr = 115242
 
−
| pages = 503–520
 
−
| title = Mathematical models for ranking from paired comparisons
 
−
| volume = 55
 
−
| year = 1960| issue = 291
 
−
| hdl = 2027/mdp.39015095254010
 
−
| hdl-access = free
 
−
}}</ref>
 
−
 
 
−
<ref name=bs97>{{citation
 
−
| last1 = Berger | first1 = Bonnie | author1-link = Bonnie Berger
 
−
| last2 = Shor | first2 = Peter W. | author2-link = Peter Shor
 
−
| doi = 10.1006/jagm.1997.0864
 
−
| issue = 1
 
−
| journal = Journal of Algorithms
 
−
| mr = 1474592
 
−
| pages = 1–18
 
−
| title = Tight bounds for the maximum acyclic subgraph problem
 
−
| volume = 25
 
−
| year = 1997}}</ref>
 
−
 
 
−
<ref name=cfr>{{citation
 
−
| last1 = Coppersmith | first1 = Don | author1-link = Don Coppersmith
 
−
| last2 = Fleischer | first2 = Lisa K.
 
−
| last3 = Rurda | first3 = Atri
 
−
| doi = 10.1145/1798596.1798608
 
−
| issue = 3
 
−
| journal = [[ACM Transactions on Algorithms]]
 
−
| mr = 2682624
 
−
| page = A55:1–A55:13
 
−
| title = Ordering by weighted number of wins gives a good ranking for weighted tournaments
 
−
| volume = 6
 
−
| year = 2010| s2cid = 18416 }}</ref>
 
−
 
 
−
<ref name=cllor>{{citation
 
−
| last1 = Chen | first1 = Jianer
 
−
| last2 = Liu | first2 = Yang
 
−
| last3 = Lu | first3 = Songjian
 
−
| last4 = O'Sullivan | first4 = Barry
 
−
| last5 = Razgon | first5 = Igor
 
−
| doi = 10.1145/1411509.1411511
 
−
| issue = 5
 
−
| pages = 1–19
 
−
| journal = [[Journal of the ACM]]
 
−
| title = A fixed-parameter algorithm for the directed feedback vertex set problem
 
−
| volume = 55
 
−
| year = 2008| s2cid = 1547510
 
−
}}</ref>
 
−
 
 
−
<ref name=clock>{{citation
 
−
| last1 = Feehrer | first1 = John R.
 
−
| last2 = Jordan | first2 = Harry F.
 
−
| date = December 1995
 
−
| doi = 10.1364/ao.34.008125
 
−
| issue = 35
 
−
| journal = Applied Optics
 
−
| title = Placement of clock gates in time-of-flight optoelectronic circuits
 
−
| volume = 34| pages = 8125–8136
 
−
| pmid = 21068927
 
−
| bibcode = 1995ApOpt..34.8125F
 
−
}}</ref>
 
−
 
 
−
<ref name=cockroach>{{citation
 
−
| last = Eickwort | first = George C.
 
−
| contribution = Dominance in a cockroach (Nauphoeta)
 
−
| date = April 2019
 
−
| doi = 10.1201/9780429049262-18
 
−
| pages = 120–126
 
−
| publisher = CRC Press
 
−
| title = Insect Behavior| s2cid = 203898549
 
−
}}</ref>
 
−
 
 
−
<ref name=compendium>{{citation
 
−
| last1 = Crescenzi
 
−
| first1 = Pierluigi
 
−
| last2 = Kann
 
−
| first2 = Viggo
 
−
| last3 = Halldórsson
 
−
| first3 = Magnús
 
−
| last4 = Karpinski
 
−
| first4 = Marek
 
−
| author4-link = Marek Karpinski
 
−
| last5 = Woeginger
 
−
| first5 = Gerhard
 
−
| author5-link = Gerhard J. Woeginger
 
−
| contribution = Minimum Feedback Arc Set
 
−
| contribution-url = https://www.csc.kth.se/~viggo/wwwcompendium/node20.html
 
−
| title = A compendium of NP optimization problems
 
−
| year = 2000
 
−
| access-date = 2021-07-29
 
−
| archive-date = 2021-07-29
 
−
| archive-url = https://web.archive.org/web/20210729012734/https://www.csc.kth.se/~viggo/wwwcompendium/node20.html
 
−
| url-status = live
 
−
}}</ref>
 
−
 
 
−
<ref name=cty>{{citation
 
−
| last1 = Charbit | first1 = Pierre
 
−
| last2 = Thomassé | first2 = Stéphan
 
−
| last3 = Yeo | first3 = Anders
 
−
| doi = 10.1017/S0963548306007887
 
−
| issue = 1
 
−
| journal = Combinatorics, Probability and Computing
 
−
| mr = 2282830
 
−
| pages = 1–4
 
−
| title = The minimum feedback arc set problem is NP-hard for tournaments
 
−
| volume = 16
 
−
| year = 2007| s2cid = 36539840
 
−
| url = https://hal-lirmm.ccsd.cnrs.fr/lirmm-00140321/file/feedback.pdf
 
−
}}</ref>
 
−
 
 
−
<ref name=dett98>{{citation
 
−
| last1 = Di Battista | first1 = Giuseppe
 
−
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
 
−
| last3 = Tamassia | first3 = Roberto | author3-link = Roberto Tamassia
 
−
| last4 = Tollis | first4 = Ioannis G.
 
−
| contribution = Layered Drawings of Digraphs
 
−
| isbn = 9780133016154
 
−
| pages = 265–302
 
−
| publisher = [[Prentice Hall]]
 
−
| title = Graph Drawing: Algorithms for the Visualization of Graphs
 
−
| year = 1998}}</ref>
 
−
 
 
−
<ref name=df01>{{citation
 
−
| last1 = Demetrescu | first1 = Camil
 
−
| last2 = Finocchi | first2 = Irene
 
−
| journal = ACM Journal of Experimental Algorithmics
 
−
| mr = 2027115
 
−
| pages = 171–182
 
−
| title = Break the "right" cycles and get the "best" drawing
 
−
| volume = 6
 
−
| year = 2001}}</ref>
 
−
 
 
−
<ref name=drafthorse>{{citation
 
−
| last1 = Estep | first1 = D.Q.
 
−
| last2 = Crowell-Davis | first2 = S.L.
 
−
| last3 = Earl-Costello | first3 = S.-A.
 
−
| last4 = Beatey | first4 = S.A.
 
−
| date = January 1993
 
−
| doi = 10.1016/0168-1591(93)90137-e
 
−
| issue = 3
 
−
| journal = Applied Animal Behaviour Science
 
−
| pages = 199–213
 
−
| title = Changes in the social behaviour of drafthorse (Equus caballus) mares coincident with foaling
 
−
| volume = 35}}</ref>
 
−
 
 
−
<ref name=ds05>{{citation
 
−
| last1 = Dinur
 
−
| first1 = Irit
 
−
| author1-link = Irit Dinur
 
−
| last2 = Safra
 
−
| first2 = Samuel
 
−
| author2-link = Shmuel Safra
 
−
| doi = 10.4007/annals.2005.162.439
 
−
| doi-access = free
 
−
| issue = 1
 
−
| journal = [[Annals of Mathematics]]
 
−
| pages = 439–485
 
−
| title = On the hardness of approximating minimum vertex cover
 
−
| url = https://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf
 
−
| volume = 162
 
−
| year = 2005
 
−
| access-date = 2021-07-29
 
−
| archive-date = 2009-09-20
 
−
| archive-url = https://web.archive.org/web/20090920071048/http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf
 
−
| url-status = live
 
−
}}; preliminary version in {{citation
 
−
| last1 = Dinur | first1 = Irit | author1-link = Irit Dinur
 
−
| last2 = Safra | first2 = Samuel | author2-link = Shmuel Safra
 
−
| editor-last = Reif | editor-first = John H. | editor-link = John Reif
 
−
| contribution = The importance of being biased
 
−
| doi = 10.1145/509907.509915
 
−
| pages = 33–42
 
−
| title = Proceedings of the 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada
 
−
| year = 2002| s2cid = 1235048 }}</ref>
 
−
 
 
−
<ref name=els>{{citation
 
−
| last1 = Eades
 
−
| first1 = Peter
 
−
| author1-link = Peter Eades
 
−
| last2 = Lin
 
−
| first2 = Xuemin
 
−
| last3 = Smyth
 
−
| first3 = W. F.
 
−
| doi = 10.1016/0020-0190(93)90079-O
 
−
| issue = 6
 
−
| journal = Information Processing Letters
 
−
| mr = 1256786
 
−
| pages = 319–323
 
−
| title = A fast and effective heuristic for the feedback arc set problem
 
−
| url = https://researchrepository.murdoch.edu.au/id/eprint/27510/
 
−
| volume = 47
 
−
| year = 1993
 
−
| access-date = 2021-08-01
 
−
| archive-date = 2020-10-22
 
−
| archive-url = https://web.archive.org/web/20201022190759/https://researchrepository.murdoch.edu.au/id/eprint/27510/
 
−
| url-status = live
 
−
}}</ref>
 
−
 
 
−
<ref name=enss>{{citation
 
−
| last1 = Even | first1 = G.
 
−
| last2 = Naor | first2 = J. | author2-link = Joseph Seffi Naor
 
−
| last3 = Schieber | first3 = B. | author3-link = Baruch Schieber
 
−
| last4 = Sudan | first4 = M. | author4-link = Madhu Sudan
 
−
| doi = 10.1007/PL00009191
 
−
| issue = 2
 
−
| journal = [[Algorithmica]]
 
−
| mr = 1484534
 
−
| pages = 151–174
 
−
| title = Approximating minimum feedback sets and multicuts in directed graphs
 
−
| volume = 20
 
−
| year = 1998| s2cid = 2437790
 
−
}}</ref>
 
−
 
 
−
<ref name=fdlv>{{citation
 
−
| last = Fernandez de la Vega | first = W.
 
−
| doi = 10.1016/0095-8956(83)90060-6
 
−
| issue = 3
 
−
| journal = Journal of Combinatorial Theory
 
−
| mr = 735201
 
−
| pages = 328–332
 
−
| series = Series B
 
−
| title = On the maximum cardinality of a consistent set of arcs in a random tournament
 
−
| volume = 35
 
−
| year = 1983| doi-access = free
 
−
}}</ref>
 
−
 
 
−
<ref name=fivb>{{citation|url=http://rio2016.fivb.com/en/beachvolleyball/men/results%20and%20rankings/maindraw|title=Main draw – Men|work=Rio 2016|publisher=[[Fédération Internationale de Volleyball]]|access-date=2021-11-14|archive-date=2016-12-23|archive-url=https://web.archive.org/web/20161223070422/http://rio2016.fivb.com/en/beachvolleyball/men/results%20and%20rankings/maindraw|url-status=live}}</ref>
 
−
 
 
−
<ref name=frank>{{citation
 
−
| last = Frank | first = András | author-link = András Frank
 
−
| doi = 10.1007/BF02579270
 
−
| issue = 2
 
−
| journal = [[Combinatorica]]
 
−
| mr = 625547
 
−
| pages = 145–153
 
−
| title = How to make a digraph strongly connected
 
−
| volume = 1
 
−
| year = 1981| s2cid = 27825518 }}</ref>
 
−
 
 
−
<ref name=gab93>{{citation
 
−
| last = Gabow | first = Harold N. | author-link = Harold N. Gabow
 
−
| contribution = A framework for cost-scaling algorithms for submodular flow problems
 
−
| doi = 10.1109/SFCS.1993.366842
 
−
| mr = 1328441
 
−
| pages = 449–458
 
−
| publisher = IEEE Computer Society
 
−
| title = 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993
 
−
| year = 1993| s2cid = 32162097 }}</ref>
 
−
 
 
−
<ref name=gab95>{{citation
 
−
| last = Gabow | first = Harold N. | author-link = Harold N. Gabow
 
−
| doi = 10.1006/jagm.1995.1022
 
−
| issue = 3
 
−
| journal = Journal of Algorithms
 
−
| mr = 1334365
 
−
| pages = 586–628
 
−
| title = Centroids, representations, and submodular flows
 
−
| volume = 18
 
−
| year = 1995}}</ref>
 
−
 
 
−
<ref name=ghmrc>{{citation
 
−
| last1 = Guruswami
 
−
| first1 = Venkatesan
 
−
| author1-link = Venkatesan Guruswami
 
−
| last2 = Håstad
 
−
| first2 = Johan
 
−
| author2-link = Johan Håstad
 
−
| last3 = Manokaran
 
−
| first3 = Rajsekar
 
−
| last4 = Raghavendra
 
−
| first4 = Prasad
 
−
| last5 = Charikar
 
−
| first5 = Moses
 
−
| author5-link = Moses Charikar
 
−
| doi = 10.1137/090756144
 
−
| issue = 3
 
−
| journal = [[SIAM Journal on Computing]]
 
−
| mr = 2823511
 
−
| pages = 878–914
 
−
| title = Beating the random ordering is hard: every ordering CSP is approximation resistant
 
−
| url = https://www.csc.kth.se/~rajsekar/papers/ocsp.pdf
 
−
| volume = 40
 
−
| year = 2011
 
−
| access-date = 2021-07-31
 
−
| archive-date = 2021-07-31
 
−
| archive-url = https://web.archive.org/web/20210731191245/https://www.csc.kth.se/~rajsekar/papers/ocsp.pdf
 
−
| url-status = live
 
−
}}</ref>
 
−
 
 
−
<ref name=gj79>{{citation
 
−
| last1 = Garey | first1 = Michael R. | author1-link = Michael R. Garey
 
−
| last2 = Johnson | first2 = David S. | author2-link = David S. Johnson
 
−
| contribution = A1.1: GT8
 
−
| isbn = 0-7167-1045-5
 
−
| page = 192
 
−
| publisher = W.H. Freeman
 
−
| title = Computers and Intractability: A Guide to the Theory of NP-Completeness
 
−
| title-link = Computers and Intractability: A Guide to the Theory of NP-Completeness
 
−
| year = 1979}}</ref>
 
−
 
 
−
<ref name=gjr85>{{citation
 
−
| last1 = Grötschel | first1 = Martin | author1-link = Martin Grötschel
 
−
| last2 = Jünger | first2 = Michael
 
−
| last3 = Reinelt | first3 = Gerhard
 
−
| doi = 10.1007/BF01582009
 
−
| issue = 1
 
−
| journal = [[Mathematical Programming]]
 
−
| mr = 809747
 
−
| pages = 28–42
 
−
| title = On the acyclic subgraph polytope
 
−
| volume = 33
 
−
| year = 1985| s2cid = 206798683 }}</ref>
 
−
 
 
−
<ref name=goddard>{{citation
 
−
| last = Goddard | first = Stephen T.
 
−
| doi = 10.1287/mnsc.29.12.1384
 
−
| issue = 12
 
−
| journal = [[Management Science (journal)|Management Science]]
 
−
| mr = 809110
 
−
| pages = 1384–1392
 
−
| title = Ranking in tournaments and group decisionmaking
 
−
| volume = 29
 
−
| year = 1983}}; note that the algorithm suggested by Goddard for finding minimum-violation rankings is incorrect</ref>
 
−
 
 
−
<ref name=hba>{{citation
 
−
| last1 = Hanauer | first1 = Kathrin
 
−
| last2 = Brandenburg | first2 = Franz-Josef
 
−
| last3 = Auer | first3 = Christopher
 
−
| editor1-last = Brandstädt | editor1-first = Andreas
 
−
| editor2-last = Jansen | editor2-first = Klaus
 
−
| editor3-last = Reischuk | editor3-first = Rüdiger
 
−
| contribution = Tight upper bounds for minimum feedback arc sets of regular graphs
 
−
| doi = 10.1007/978-3-642-45043-3_26
 
−
| mr = 3139198
 
−
| pages = 298–309
 
−
| publisher = Springer
 
−
| series = Lecture Notes in Computer Science
 
−
| title = Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers
 
−
| volume = 8165
 
−
| year = 2013}}</ref>
 
−
 
 
−
<ref name=Hecht>{{citation
 
−
| last1 = Hecht | first1 = Michael
 
−
| arxiv = 1702.07612
 
−
| doi = 10.1007/s00224-017-9777-6
 
−
| journal = [[Theory of Computing Systems]]
 
−
| volume = 62
 
−
| issue = 5
 
−
| pages = 1048–1084
 
−
| title = Exact localisations of feedback sets
 
−
| year = 2017| s2cid = 18394348
 
−
}}</ref>
 
−
 
 
−
<ref name=hmssy>{{citation
 
−
| last1 = Huang | first1 = Hao
 
−
| last2 = Ma | first2 = Jie
 
−
| last3 = Shapira | first3 = Asaf
 
−
| last4 = Sudakov | first4 = Benny | author4-link = Benny Sudakov
 
−
| last5 = Yuster | first5 = Raphael
 
−
| doi = 10.1017/S0963548313000394
 
−
| issue = 6
 
−
| journal = Combinatorics, Probability and Computing
 
−
| mr = 3111546
 
−
| pages = 859–873
 
−
| title = Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
 
−
| volume = 22
 
−
| year = 2013| arxiv = 1202.2602
 
−
| hdl = 20.500.11850/73894
 
−
| s2cid = 7967738
 
−
| hdl-access = free
 
−
}}</ref>
 
−
 
 
−
<ref name=hr94>{{citation
 
−
| last1 = Hassin | first1 = Refael
 
−
| last2 = Rubinstein | first2 = Shlomi
 
−
| doi = 10.1016/0020-0190(94)00086-7
 
−
| issue = 3
 
−
| journal = Information Processing Letters
 
−
| mr = 1290207
 
−
| pages = 133–140
 
−
| title = Approximations for the maximum acyclic subgraph problem
 
−
| volume = 51
 
−
| year = 1994}}</ref>
 
−
 
 
−
<ref name=hubert>{{citation
 
−
| last = Hubert | first = Lawrence | author-link = Lawrence Hubert
 
−
| doi = 10.1111/j.2044-8317.1976.tb00701.x
 
−
| issue = 1
 
−
| journal = [[British Journal of Mathematical and Statistical Psychology]]
 
−
| mr = 0429180
 
−
| pages = 32–52
 
−
| title = Seriation using asymmetric proximity measures
 
−
| volume = 29
 
−
| year = 1976}}</ref>
 
−
 
 
−
<ref name=in04>{{citation
 
−
| last1 = Isaak | first1 = Garth
 
−
| last2 = Narayan | first2 = Darren A.
 
−
| doi = 10.1016/j.ipl.2004.07.001
 
−
| issue = 3
 
−
| journal = Information Processing Letters
 
−
| mr = 2095357
 
−
| pages = 107–111
 
−
| title = A classification of tournaments having an acyclic tournament as a minimum feedback arc set
 
−
| volume = 92
 
−
| year = 2004| url = https://scholarworks.rit.edu/article/1119
 
−
}}</ref>
 
−
 
 
−
<ref name=kann>{{citation
 
−
| last = Kann
 
−
| first = Viggo
 
−
| publisher = Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm
 
−
| title = On the Approximability of NP-complete Optimization Problems
 
−
| type = Ph.D. thesis
 
−
| url = http://www.nada.kth.se/~viggo/papers/phdthesis.pdf
 
−
| year = 1992
 
−
| access-date = 2007-10-11
 
−
| archive-date = 2010-12-29
 
−
| archive-url = https://web.archive.org/web/20101229064746/http://www.nada.kth.se/~viggo/papers/phdthesis.pdf
 
−
| url-status = live
 
−
}}</ref>
 
−
 
 
−
<ref name=karp>{{citation
 
−
| last = Karp | first = Richard M. | author-link = Richard M. Karp
 
−
| contribution = Reducibility among combinatorial problems
 
−
| location = New York
 
−
| pages = 85–103
 
−
| publisher = Plenum
 
−
| series = Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.
 
−
| title = Complexity of Computer Computations
 
−
| year = 1972}}</ref>
 
−
 
 
−
<ref name=KarpinskiSchudy>{{citation
 
−
| last1 = Karpinski | first1 = Marek | author1-link = Marek Karpinski
 
−
| last2 = Schudy | first2 = Warren
 
−
| arxiv = 1006.4396
 
−
| editor1-last = Cheong | editor1-first = Otfried | editor1-link = Otfried Cheong
 
−
| editor2-last = Chwa | editor2-first = Kyung-Yong
 
−
| editor3-last = Park | editor3-first = Kunsoo
 
−
| contribution = Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
 
−
| doi = 10.1007/978-3-642-17517-6_3
 
−
| pages = 3–14
 
−
| publisher = Springer
 
−
| series = Lecture Notes in Computer Science
 
−
| title = Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I
 
−
| volume = 6506
 
−
| year = 2010| s2cid = 16512997 }}</ref>
 
−
 
 
−
<ref name=kemeny>{{citation
 
−
| last = Kemeny | first = John G. | author-link = John G. Kemeny
 
−
| date = Fall 1959
 
−
| issue = 4
 
−
| journal = [[Daedalus (journal)|Daedalus]]
 
−
| jstor = 20026529
 
−
| pages = 577–591
 
−
| title = Mathematics without numbers
 
−
| volume = 88}}</ref>
 
−
 
 
−
<ref name=lawler>{{citation
 
−
| last = Lawler | first = E. | author-link = Eugene Lawler
 
−
| doi = 10.1109/tct.1964.1082291
 
−
| issue = 2
 
−
| journal = [[IEEE Transactions on Circuit Theory]]
 
−
| pages = 296–297
 
−
| title = A comment on minimum feedback arc sets
 
−
| volume = 11
 
−
| year = 1964}}</ref>
 
−
 
 
−
<ref name=lovasz>{{citation
 
−
| last = Lovász | first = László | author-link = László Lovász
 
−
| doi = 10.1016/0095-8956(76)90049-6
 
−
| issue = 2
 
−
| journal = [[Journal of Combinatorial Theory]]
 
−
| mr = 427138
 
−
| pages = 96–103
 
−
| series = Series B
 
−
| title = On two minimax theorems in graph
 
−
| volume = 21
 
−
| year = 1976| doi-access = free
 
−
}}</ref>
 
−
 
 
−
<ref name=ls89>{{citation
 
−
| last1 = Lin | first1 = Lishin
 
−
| last2 = Sahni | first2 = Sartaj | author2-link = Sartaj Sahni
 
−
| doi = 10.1109/12.24280
 
−
| issue = 5
 
−
| journal = [[IEEE Transactions on Computers]]
 
−
| mr = 994519
 
−
| pages = 756–761
 
−
| title = Fair edge deletion problems
 
−
| volume = 38
 
−
| year = 1989}}</ref>
 
−
 
 
−
<ref name=ly78>{{citation
 
−
| last1 = Lucchesi | first1 = C. L.
 
−
| last2 = Younger | first2 = D. H.
 
−
| doi = 10.1112/jlms/s2-17.3.369
 
−
| issue = 3
 
−
| journal = Journal of the London Mathematical Society
 
−
| mr = 500618
 
−
| pages = 369–374
 
−
| series = Second Series
 
−
| title = A minimax theorem for directed graphs
 
−
| volume = 17
 
−
| year = 1978}}</ref>
 
−
 
 
−
<ref name=MathieuSchudy>{{citation
 
−
| last1 = Kenyon-Mathieu | first1 = Claire | author1-link = Claire Mathieu
 
−
| last2 = Schudy | first2 = Warren
 
−
| editor1-last = Johnson | editor1-first = David S. | editor1-link = David S. Johnson
 
−
| editor2-last = Feige | editor2-first = Uriel | editor2-link = Uriel Feige
 
−
| contribution = How to rank with few errors: a PTAS for weighted feedback arc set on tournaments
 
−
| doi = 10.1145/1250790.1250806
 
−
| id = {{ECCC|2006|06|144}}
 
−
| pages = 95–103
 
−
| title = Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007
 
−
| year = 2007| s2cid = 9436948 }}; see also [http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf author's extended version] {{Webarchive|url=https://web.archive.org/web/20090115232215/http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf |date=2009-01-15 }}</ref>
 
−
 
 
−
<ref name=minoura>{{citation
 
−
| last = Minoura | first = Toshimi
 
−
| doi = 10.1145/322344.322351
 
−
| issue = 4
 
−
| journal = [[Journal of the ACM]]
 
−
| mr = 674256
 
−
| pages = 1023–1048
 
−
| title = Deadlock avoidance revisited
 
−
| volume = 29
 
−
| year = 1982| s2cid = 5284738
 
−
}}</ref>
 
−
 
 
−
<ref name=missik>{{citation
 
−
| last1 = Mishra | first1 = Sounaka
 
−
| last2 = Sikdar | first2 = Kripasindhu
 
−
| doi = 10.1016/S0166-218X(03)00444-X
 
−
| issue = 2–3
 
−
| journal = [[Discrete Applied Mathematics]]
 
−
| mr = 2045215
 
−
| pages = 249–269
 
−
| title = On approximability of linear ordering and related NP-optimization problems on graphs
 
−
| volume = 136
 
−
| year = 2004}}</ref>
 
−
 
 
−
<ref name=newman>{{citation
 
−
| last = Newman | first = Alantha
 
−
| date = June 2000
 
−
| hdl = 1721.1/86548
 
−
| publisher = Massachusetts Institute of Technology
 
−
| title = Approximating the maximum acyclic subgraph
 
−
| type = Master’s thesis}}, as cited by {{harvtxt|Guruswami|Håstad|Manokaran|Raghavendra|Charikar|2011}}</ref>
 
−
 
 
−
<ref name=np00>{{citation
 
−
| last1 = Nutov | first1 = Zeev
 
−
| last2 = Penn | first2 = Michal
 
−
| doi = 10.1023/A:1009802905533
 
−
| issue = 2
 
−
| journal = Journal of Combinatorial Optimization
 
−
| mr = 1772828
 
−
| pages = 235–251
 
−
| title = On integrality, stability and composition of dicycle packings and covers
 
−
| volume = 4
 
−
| year = 2000| s2cid = 207632524
 
−
}}</ref>
 
−
 
 
−
<ref name=pa92>{{citation
 
−
| last1 = Park | first1 = S.
 
−
| last2 = Akers | first2 = S.B.
 
−
| contribution = An efficient method for finding a minimal feedback arc set in directed graphs
 
−
| doi = 10.1109/iscas.1992.230449
 
−
| pages = 1863–1866
 
−
| title = Proceedings of the 1992 IEEE International Symposium on Circuits and Systems (ISCAS '92)
 
−
| volume = 4
 
−
| year = 1992| s2cid = 122603659
 
−
}}</ref>
 
−
 
 
−
<ref name=ramachandran>{{citation
 
−
| last = Ramachandran | first = Vijaya | author-link = Vijaya Ramachandran
 
−
| doi = 10.1016/0196-6774(88)90022-3
 
−
| issue = 3
 
−
| journal = Journal of Algorithms
 
−
| mr = 955140
 
−
| pages = 299–313
 
−
| title = Finding a minimum feedback arc set in reducible flow graphs
 
−
| volume = 9
 
−
| year = 1988}}</ref>
 
−
 
 
−
<ref name=rh68>{{citation
 
−
| last1 = Rosen
 
−
| first1 = Edward M.
 
−
| last2 = Henley
 
−
| first2 = Ernest J.
 
−
| date = Summer 1968
 
−
| issue = 3
 
−
| journal = Chemical Engineering Education
 
−
| pages = 120–125
 
−
| title = The New Stoichiometry
 
−
| url = https://journals.flvc.org/cee/article/view/127098
 
−
| volume = 2
 
−
| access-date = 2021-08-02
 
−
| archive-date = 2021-08-02
 
−
| archive-url = https://web.archive.org/web/20210802021016/https://journals.flvc.org/cee/article/view/127098
 
−
| url-status = live
 
−
}}</ref>
 
−
 
 
−
<ref name=rt64>{{citation
 
−
| last1 = Thompson | first1 = W. A., Jr.
 
−
| last2 = Remage | first2 = Russell, Jr.
 
−
| doi = 10.1214/aoms/1177703572
 
−
| journal = [[Annals of Mathematical Statistics]]
 
−
| jstor = 2238526
 
−
| mr = 161419
 
−
| pages = 739–747
 
−
| title = Rankings from paired comparisons
 
−
| volume = 35
 
−
| year = 1964| issue = 2
 
−
}}</ref>
 
−
 
 
−
<ref name=rt66>{{citation
 
−
| last1 = Remage | first1 = Russell Jr.
 
−
| last2 = Thompson | first2 = W. A. Jr.
 
−
| doi = 10.1093/biomet/53.1-2.143
 
−
| journal = [[Biometrika]]
 
−
| jstor = 2334060
 
−
| mr = 196854
 
−
| pages = 143–149
 
−
| title = Maximum-likelihood paired comparison rankings
 
−
| volume = 53
 
−
| year = 1966| issue = 1–2
 
−
| pmid = 5964054
 
−
}}</ref>
 
−
 
 
−
<ref name=seyfarth>{{citation
 
−
| last = Seyfarth | first = Robert M.
 
−
| date = November 1976
 
−
| doi = 10.1016/s0003-3472(76)80022-x
 
−
| issue = 4
 
−
| journal = Animal Behaviour
 
−
| pages = 917–938
 
−
| title = Social relationships among adult female baboons
 
−
| volume = 24| s2cid = 54284406
 
−
}}</ref>
 
−
 
 
−
<ref name=slater>{{citation
 
−
| last = Slater | first = Patrick
 
−
| doi = 10.1093/biomet/48.3-4.303
 
−
| issue = 3–4
 
−
| journal = [[Biometrika]]
 
−
| jstor = 2332752
 
−
| pages = 303–312
 
−
| title = Inconsistencies in a schedule of paired comparisons
 
−
| volume = 48
 
−
| year = 1961}}</ref>
 
−
 
 
−
<ref name=spencer>{{citation
 
−
| last = Spencer | first = J. | author-link = Joel Spencer
 
−
| doi = 10.1007/BF02017965
 
−
| issue = 2
 
−
| journal = Periodica Mathematica Hungarica
 
−
| mr = 573525
 
−
| pages = 131–144
 
−
| title = Optimally ranking unrankable tournaments
 
−
| volume = 11
 
−
| year = 1980| s2cid = 119894999 }}</ref>
 
−
 
 
−
<ref name=ss02>{{citation
 
−
| last1 = Schwikowski | first1 = Benno
 
−
| last2 = Speckenmeyer | first2 = Ewald
 
−
| doi = 10.1016/S0166-218X(00)00339-5
 
−
| issue = 1–3
 
−
| journal = [[Discrete Applied Mathematics]]
 
−
| mr = 1881280
 
−
| pages = 253–265
 
−
| title = On enumerating all minimal solutions of feedback problems
 
−
| volume = 117
 
−
| year = 2002| doi-access = free
 
−
}}</ref>
 
−
 
 
−
<ref name=unger>{{citation
 
−
| last = Unger | first = Stephen H.
 
−
| date = April 26, 1957
 
−
| hdl = 1721.1/4763
 
−
| publisher = Massachusetts Institute of Technology, Research Laboratory of Electronics
 
−
| series = Technical reports
 
−
| title = A study of asynchronous logical feedback networks
 
−
| volume = 320}}</ref>
 
−
 
 
−
<ref name=vdym>{{citation
 
−
| last1 = Vaziri | first1 = Baback
 
−
| last2 = Dabadghao | first2 = Shaunak
 
−
| last3 = Yih | first3 = Yuehwern
 
−
| last4 = Morin | first4 = Thomas L.
 
−
| date = January 2018
 
−
| doi = 10.1057/s41274-017-0266-8
 
−
| issue = 5
 
−
| journal = Journal of the Operational Research Society
 
−
| pages = 776–787
 
−
| title = Properties of sports ranking methods
 
−
| volume = 69| s2cid = 51887586
 
−
}}</ref>
 
−
 
 
−
<ref name=younger>{{citation
 
−
| last = Younger | first = D.
 
−
| doi = 10.1109/tct.1963.1082116
 
−
| issue = 2
 
−
| journal = IEEE Transactions on Circuit Theory
 
−
| pages = 238–245
 
−
| title = Minimum feedback arc sets for a directed graph
 
−
| volume = 10
 
−
| year = 1963}}</ref>
 
−
 
 
−
}}
 
−
 
 
−
{{DEFAULTSORT:Feedback Arc Set}}
 
−
[[Category:Directed graphs]]
 
−
[[Category:Graph theory objects]]
 
−
[[Category:NP-complete problems]]
 
−
[[Category:Computational problems in graph theory]]
 

Latest revision as of 00:22, 23 February 2022

Retrieved from "https://wiki.tachyony.co.uk/w/index.php?title=Feedback_arc_set&oldid=11854"