2322:, 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. 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
302:, 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. Feedback arc sets have also been used for a different subproblem of layered graph drawing, the ordering of vertices within consecutive pairs of layers.
172:
1891:
179:, 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.
203:, 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. Many sports use simpler methods for
229:, 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. Alternatively, if these comparisons result in independent probabilities for each pairwise ordering, then the
33:
498:
313:, 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. 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.
1898:
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
330:
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
541:
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. When one of these components can be separated into two
493:
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
1845:
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
263:
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. This can be formulated and solved as a minimum-weight feedback arc set problem, in which the vertices represent candidates, edges are
272:
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
294:
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".
1249:
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
1195:
This means that the size of the feedback arc set that it finds is at most this factor larger than the optimum. Determining whether feedback arc set has a constant-ratio approximation algorithm, or whether a non-constant ratio is necessary, remains an open problem.
80:
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.
2282:: the minimum size of a feedback arc set equals the maximum number of edge-disjoint directed cycles that can be found in the graph. This is not true for some other graphs; for instance the first illustration shows a directed version of the non-planar graph
4094:
Bonamy, Marthe; Kowalik, Lukasz; Nederlof, Jesper; Pilipczuk, Michal; Socala, Arkadiusz; Wrochna, Marcin (2018), "On directed feedback vertex set parameterized by treewidth", in
Brandstädt, Andreas; Köhler, Ekkehard; Meer, Klaus (eds.),
2072:
from vertex cover to feedback arc set, which preserves the quality of approximations. 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.
2043:
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.
277:
made from asynchronous components, synchronization can be achieved by placing clocked gates on the edges of a feedback arc set. Additionally, cutting a circuit on a feedback arc a set reduces the remaining circuit to
736:, 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
554:
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. Searching all
2084:
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
5551:
Hanauer, Kathrin; Brandenburg, Franz-Josef; Auer, Christopher (2013), "Tight upper bounds for minimum feedback arc sets of regular graphs", in
Brandstädt, Andreas; Jansen, Klaus; Reischuk, Rüdiger (eds.),
1523:
1857:, which generalizes to a weighted version of the problem. A subexponential parameterized algorithm for weighted feedback arc sets on tournaments is also known. The maximum acyclic subgraph problem for
1826:, using the fact that the triconnected components of these graphs are either planar or of bounded size. Planar graphs have also been generalized in a different way to a class of directed graphs called
264:
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.
1103:
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
2400:
385:
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
2068:, 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
529:, 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.
4838:
1465:
176:
2562:
2482:
2217:
2120:
1384:
1238:
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.
1004:
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
282:, 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. Similarly, in
2267:
2064:, 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
3172:
Estep, D.Q.; Crowell-Davis, S.L.; Earl-Costello, S.-A.; Beatey, S.A. (January 1993), "Changes in the social behaviour of drafthorse (Equus caballus) mares coincident with foaling",
1191:
846:
721:
976:
60:
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 an
2763:
2182:
2150:
1782:
1658:
1907:
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
1228:
921:
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
1072:
1551:
665:
2922:
2018:
1698:
2313:
1820:
1408:
1330:
614:
2861:
2813:
1838:. 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.
1579:
222:
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.
2833:
2785:
2702:
2682:
2651:
2629:
2607:
2587:
1973:
1951:
1929:
1722:
1288:
1268:
1098:
1030:
998:
914:
890:
868:
780:
758:
578:
523:
491:
471:
449:
425:
403:
381:
352:
4006:; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012), "A note on exact algorithms for vertex ordering problems on graphs",
2892:
542:
disconnected subgraphs by removing two vertices, a more complicated decomposition applies, allowing the problem to be split into subproblems derived from the
4058:
Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem",
850:
by transforming it into an equivalent feedback vertex set problem and applying a parameterized feedback vertex set algorithm. Because the exponent of
4718:
1034:
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
128:, and maximum acyclic subgraphs can be approximated to within a constant factor. Both are hard to approximate closer than some constant factor, an
5613:
3276:
2888:
3309:; published in preliminary form as ASTIA Document No. AD 206 573, United States Air Force, Office of Scientific Research, November 1958,
1605:. This dual problem is polynomially solvable, and therefore the planar minimum feedback arc set problem is as well. It can be solved in
4297:
4730:
252:
of arranging elements into a linear ordering, in cases where data is available that provides pairwise comparisons between the elements.
5554:
Graph-Theoretic
Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers
4245:
3773:
Mishra, Sounaka; Sikdar, Kripasindhu (2004), "On approximability of linear ordering and related NP-optimization problems on graphs",
3411:; Schudy, Warren (2010), "Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament", in
4097:
Graph-Theoretic
Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings
3417:
Algorithms and
Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I
1133:
17:
1472:
36:
Partition of a directed graph into a minimum feedback arc set (red dashed edges) and a maximum acyclic subgraph (blue solid edges)
4956:
2609:
is the unique minimum feedback arc set of the tournament. The size of this tournament has been defined as the "reversing number"
5000:
4792:
3545:
3094:; Fleischer, Lisa K.; Rurda, Atri (2010), "Ordering by weighted number of wins gives a good ranking for weighted tournaments",
2315:
in which the minimum size of a feedback arc set is two, while the maximum number of edge-disjoint directed cycles is only one.
2056:
is defined as consisting of optimization problems that have a polynomial time approximation algorithm that achieves a constant
326:
The minimum feedback arc set and maximum acyclic subgraph are equivalent for the purposes of exact optimization, as one is the
5170:
5058:
5569:
4122:
3622:
3586:
3442:
3215:
5292:
4868:
1854:
5489:; Yuster, Raphael (2013), "Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs",
3490:
Feehrer, John R.; Jordan, Harry F. (December 1995), "Placement of clock gates in time-of-flight optoelectronic circuits",
673:
that tests all partitions of the vertices into two equal subsets and recurses within each subset can solve the problem in
3974:
2326:
473:
can be obtained from the solution to a minimum feedback arc set problem on a graph obtained by splitting every vertex of
2024:, implying that neither it nor the optimization problem are expected to have polynomial time algorithms. It was one of
207:
based on points awarded for each game; these methods can provide a constant approximation to the minimum-upset ranking.
187:, a directed graph with one edge between each pair of vertices. Reversing the edges of the feedback arc set produces a
1415:
5102:
4848:
4571:
3875:
3330:
2077:
2029:
2494:
2880:
2408:
533:
In both exact and approximate solutions to the feedback arc set problem, it is sufficient to solve separately each
5371:
Fernandez de la Vega, W. (1983), "On the maximum cardinality of a consistent set of arcs in a random tournament",
4999:(Ph.D. thesis), Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm,
2187:
2090:
1337:
5250:
4699:
Proceedings of the 39th Annual ACM Symposium on Theory of
Computing, San Diego, California, USA, June 11-13, 2007
3051:
204:
4689:; Schudy, Warren (2007), "How to rank with few errors: a PTAS for weighted feedback arc set on tournaments", in
4151:
3858:
Park, S.; Akers, S.B. (1992), "An efficient method for finding a minimal feedback arc set in directed graphs",
3472:, Technical reports, vol. 320, Massachusetts Institute of Technology, Research Laboratory of Electronics,
3096:
2223:
5087:
Proceedings of the 34th Annual ACM Symposium on Theory of
Computing, May 19-21, 2002, Montréal, Québec, Canada
3901:
Nutov, Zeev; Penn, Michal (2000), "On integrality, stability and composition of dicycle packings and covers",
1931:
edges). Thus, the decision version of the feedback arc set problem takes as input both a directed graph and a
1199:
The maximum acyclic subgraph problem has an easy approximation algorithm that achieves an approximation ratio
5608:
5603:
4185:
Schwikowski, Benno; Speckenmeyer, Ewald (2002), "On enumerating all minimal solutions of feedback problems",
1866:
230:
151:, is a set of vertices containing at least one vertex from every cycle in a directed or undirected graph. In
5413:
4819:, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103
4755:"A new rounding procedure for the assignment problem with applications to dense graph arrangement problems"
4187:
3775:
3015:
670:
534:
502:
2767:
There are infinitely many
Eulerian directed graphs for which this bound is tight. If a directed graph has
2060:. Although such approximations are not known for the feedback arc set problem, the problem is known to be
1146:
789:
678:
183:
Several problems involving finding rankings or orderings can be solved by finding a feedback arc set on a
3814:
2155:
1077:
926:
306:
89:
4954:; D'Atri, A.; Protasi, M. (1980), "Structure preserving reductions among convex optimization problems",
4556:
34th Annual
Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993
2708:
2161:
2129:
1731:
4358:
Hassin, Refael; Rubinstein, Shlomi (1994), "Approximations for the maximum acyclic subgraph problem",
3601:
Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in
Kaufmann, Michael;
1610:
5145:
1850:
1204:
1139:
The best known polynomial-time approximation algorithm for the feedback arc set has the non-constant
249:
159:
are the largest acyclic subgraphs, and the number of edges removed in forming a spanning tree is the
117:
2040:, could be transformed ("reduced") into equivalent inputs to the feedback arc set decision problem.
1842:
5598:
4759:
4607:
1835:
1602:
733:
5193:
Bonnet, Édouard; Paschos, Vangelis Th. (2018), "Sparsification and subexponential approximation",
4903:
3637:
Demetrescu, Camil; Finocchi, Irene (2001), "Break the "right" cycles and get the "best" drawing",
3040:; note that the algorithm suggested by Goddard for finding minimum-violation rankings is incorrect
2961:
Remage, Russell Jr.; Thompson, W. A. Jr. (1966), "Maximum-likelihood paired comparison rankings",
1388:
Another, more complicated, polynomial time approximation algorithm applies to graphs with maximum
2081:
1127:
623:
260:
226:
133:
97:
1039:
537:
of the given graph, and to break these strongly connected components down even farther to their
2567:
2069:
1895:
1530:
631:
241:
200:
188:
65:
1978:
1667:
5039:
4269:
2285:
1792:
1393:
1293:
538:
526:
299:
5449:"A classification of tournaments having an acyclic tournament as a minimum feedback arc set"
5245:
4727:
5579:
5530:
5472:
5434:
5394:
5350:
5313:
5273:
5224:
5166:
5125:
4977:
4930:
4889:
4780:
4673:
4628:
4581:
4535:
4490:
4448:
4379:
4345:
4293:
4233:
4210:
4172:
4037:
3922:
3796:
3752:
3703:
3650:
3499:
3361:
3305:
3117:
3036:
2992:
2943:
2037:
587:
291:
287:
283:
85:
77:
4237:
8:
4649:
2838:
2790:
2787:
vertices, with at most three edges per vertex, then it has a feedback arc set of at most
2664:
and each vertex has equal numbers of incoming and outgoing edges. For such a graph, with
2057:
1862:
1556:
1140:
619:
355:
279:
274:
234:
219:
192:
148:
125:
4602:
3860:
Proceedings of the 1992 IEEE International Symposium on Circuits and Systems (ISCAS '92)
3503:
3138:
Seyfarth, Robert M. (November 1976), "Social relationships among adult female baboons",
5534:
5498:
5354:
5228:
5202:
5108:
4934:
4784:
4710:
4632:
4585:
4494:
4128:
4100:
4077:
4060:
4041:
4003:
3926:
3881:
3841:
3823:
3756:
3729:
3707:
3609:, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120,
3448:
3420:
3388:
3379:
3349:
3293:
3257:
3221:
3155:
3121:
3074:
2980:
2935:
2818:
2770:
2687:
2667:
2661:
2636:
2614:
2592:
2572:
1958:
1936:
1914:
1707:
1273:
1253:
1083:
1015:
983:
899:
875:
853:
765:
743:
563:
508:
476:
456:
434:
410:
388:
366:
337:
195:
can be used as the desired ranking. Applications of this method include the following:
4201:
3788:
3151:
2633:
and among directed acyclic graphs with the same number of vertices it is largest when
2080:
that are standard in computational complexity theory but stronger than P ≠ NP. If the
5565:
5426:
5385:
5358:
5287:
5264:
5098:
4991:
4969:
4844:
4754:
4665:
4636:
4567:
4371:
4285:
4118:
3930:
3885:
3871:
3669:
3618:
3582:
3515:
3438:
3328:
Thompson, W. A. Jr.; Remage, Russell Jr. (1964), "Rankings from paired comparisons",
3225:
3211:
3185:
2996:
2835:
edges, with at most four edges per vertex, then it has a feedback arc set of at most
2076:
The hardness of approximation of these problems has also been studied under unproven
1831:
129:
5138:"Beating the random ordering is hard: every ordering CSP is approximation resistant"
5031:
4938:
4589:
4498:
3845:
3533:
3452:
3159:
3078:
3050:
Vaziri, Baback; Dabadghao, Shaunak; Yih, Yuehwern; Morin, Thomas L. (January 2018),
171:
5557:
5538:
5516:
5508:
5460:
5422:
5380:
5338:
5301:
5259:
5232:
5212:
5154:
5137:
5112:
5090:
5048:
4965:
4951:
4918:
4877:
4834:
4830:
4788:
4768:
4714:
4702:
4690:
4661:
4616:
4559:
4523:
4478:
4436:
4400:
4367:
4333:
4281:
4196:
4160:
4132:
4110:
4081:
4069:
4045:
4023:
4015:
3983:
3952:
3910:
3863:
3833:
3784:
3760:
3738:
3711:
3691:
3610:
3570:
3507:
3473:
3430:
3339:
3315:
3310:
3285:
3249:
3203:
3181:
3147:
3105:
3066:
3024:
2972:
2931:
2319:
1908:
1890:
1246:
1108:
726:
310:
269:
184:
152:
137:
113:
5575:
5561:
5556:, Lecture Notes in Computer Science, vol. 8165, Springer, pp. 298–309,
5526:
5468:
5430:
5408:
5390:
5346:
5309:
5269:
5220:
5162:
4973:
4926:
4885:
4812:
4776:
4734:
4669:
4624:
4577:
4551:
4531:
4514:
Lucchesi, C. L.; Younger, D. H. (1978), "A minimax theorem for directed graphs",
4486:
4444:
4424:
4375:
4341:
4289:
4229:
4206:
4168:
4033:
3918:
3792:
3748:
3699:
3673:
3646:
3602:
3408:
3357:
3301:
3125:
3113:
3091:
3032:
2988:
2939:
2917:
2279:
2025:
1904:
1870:
121:
45:
5129:
5053:
4605:; Jünger, Michael; Reinelt, Gerhard (1985), "On the acyclic subgraph polytope",
4554:(1993), "A framework for cost-scaling algorithms for submodular flow problems",
4464:
4114:
4099:, Lecture Notes in Computer Science, vol. 11159, Springer, pp. 65–78,
3680:(1998), "Approximating minimum feedback sets and multicuts in directed graphs",
3434:
3274:
Brunk, H. D. (1960), "Mathematical models for ranking from paired comparisons",
3253:
2976:
1008:; it is much easier to compute than the minimum feedback arc set. For graphs of
5133:
4750:
4722:
4686:
4527:
3412:
3374:
3238:
Slater, Patrick (1961), "Inconsistencies in a schedule of paired comparisons",
3013:
Goddard, Stephen T. (1983), "Ranking in tournaments and group decisionmaking",
2589:
can be embedded as a subgraph of a larger tournament graph, in such a way that
1874:
327:
124:, the minimum feedback arc set can be approximated to within a polylogarithmic
57:
5521:
5512:
5464:
5216:
4922:
4019:
3914:
3867:
3837:
3419:, Lecture Notes in Computer Science, vol. 6506, Springer, pp. 3–14,
3344:
3070:
233:
of the overall ranking can be obtained by converting these probabilities into
5592:
5486:
5290:(1990), "Sorting, minimal feedback sets, and Hamilton paths in tournaments",
4746:
4563:
4469:
4317:
3987:
3969:
3956:
3578:
3207:
2033:
1861:
also has a polynomial-time approximation scheme. Its main ideas are to apply
1787:
1005:
256:
156:
105:
93:
5448:
4706:
4073:
3614:
3109:
3028:
2184:
the minimum feedback arc set does not have an approximation within a factor
140:, the minimum feedback arc set can be approximated more accurately, and for
5326:
5078:
5027:
4440:
4337:
4146:
3682:
3519:
1786:
These planar algorithms can be extended to the graphs that do not have the
1590:
1001:
160:
141:
41:
5094:
4772:
3743:
3198:
Eickwort, George C. (April 2019), "Dominance in a cockroach (Nauphoeta)",
3000:
1975:
edges, or equivalently whether there is an acyclic subgraph with at least
237:
and finding a minimum-weight feedback arc set in the resulting tournament.
4694:
4265:
3677:
3566:
3511:
2021:
1858:
1823:
1104:
556:
494:
preserve approximation quality for the maximum acyclic subgraph problem.
453:
In the other direction, the minimum feedback vertex set of a given graph
211:
4404:
3392:
5342:
5074:
5023:
4652:(1988), "Finding a minimum feedback arc set in reducible flow graphs",
4620:
4482:
4321:
3695:
3477:
3353:
3297:
3261:
3240:
2984:
2963:
2657:
2487:
1594:
1118:
359:
268:
Another early application of feedback arc sets concerned the design of
245:
5158:
4881:
4840:
Computers and Intractability: A Guide to the Theory of NP-Completeness
3943:
Younger, D. (1963), "Minimum feedback arc sets for a directed graph",
5082:
4863:
4164:
4028:
3171:
1010:
543:
108:. Finding minimum feedback arc sets and maximum acyclic subgraphs is
5305:
3289:
2704:
vertices, the size of a minimum feedback arc set is always at least
5124:
4409:
4105:
3828:
2061:
1107:. All minimal feedback arc sets can be listed by an algorithm with
215:
101:
32:
5503:
5207:
3425:
2815:
edges, and some graphs require this many. If a directed graph has
4904:"The minimum feedback arc set problem is NP-hard for tournaments"
4324:(1997), "Tight bounds for the maximum acyclic subgraph problem",
4270:"A fast and effective heuristic for the feedback arc set problem"
4227:
2065:
1899:
yellow vertices) corresponds to the red minimum feedback arc set.
109:
2278:
In planar directed graphs, the feedback arc set problem obeys a
3812:
Hecht, Michael (2017), "Exact localisations of feedback sets",
1598:
4093:
3564:
5411:; Tesman, Barry (1995), "The reversing number of a digraph",
3573:; Tollis, Ioannis G. (1998), "Layered Drawings of Digraphs",
1955:
It asks whether all cycles can be broken by removing at most
1702:
or when the weights are positive integers that are at most a
505:, the rightmost of which can be split at articulation vertex
4427:(1995), "Centroids, representations, and submodular flows",
4002:
2154:
Beyond polynomial time for approximation algorithms, if the
1518:{\displaystyle {\tfrac {1}{2}}+\Omega (1/{\sqrt {\Delta }})}
740:
is the size of the minimum feedback arc set. On graphs with
5406:
4993:
On the Approximability of NP-complete Optimization Problems
1849:
When the minimum feedback arc set problem is restricted to
4399:(Master's thesis), Massachusetts Institute of Technology,
2923:
British Journal of Mathematical and Statistical Psychology
4950:
3727:
Minoura, Toshimi (1982), "Deadlock avoidance revisited",
3575:
Graph Drawing: Algorithms for the Visualization of Graphs
3090:
2920:(1976), "Seriation using asymmetric proximity measures",
2053:
84:
Feedback arc sets have applications in circuit analysis,
68:. A feedback arc set with the fewest possible edges is a
4902:
Charbit, Pierre; Thomassé, Stéphan; Yeo, Anders (2007),
4228:
Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús;
918:
this algorithm is said to be fixed-parameter tractable.
497:
144:
both problems can be solved exactly in polynomial time.
5407:
Barthélémy, Jean-Pierre; Hudry, Olivier; Isaak, Garth;
5032:"On the hardness of approximating minimum vertex cover"
4184:
4057:
3049:
5550:
4601:
2499:
2413:
2331:
2219:
that can be computed in the subexponential time bound
2192:
2095:
1846:
reducibility does not require the graph to be planar.
1477:
1342:
1209:
5484:
4815:(1972), "Reducibility among combinatorial problems",
3667:
2841:
2821:
2793:
2773:
2711:
2690:
2670:
2639:
2617:
2595:
2575:
2497:
2411:
2329:
2288:
2226:
2190:
2164:
2132:
2093:
2036:
by showing that inputs for another hard problem, the
1981:
1961:
1939:
1917:
1795:
1734:
1710:
1670:
1613:
1559:
1533:
1475:
1418:
1396:
1340:
1332:
edges, in linear time, giving an approximation ratio
1296:
1276:
1256:
1207:
1149:
1086:
1042:
1018:
986:
929:
902:
878:
856:
792:
768:
746:
681:
634:
590:
566:
511:
479:
459:
437:
413:
391:
369:
340:
240:
The same maximum-likelihood ordering can be used for
5370:
5329:(1980), "Optimally ranking unrankable tournaments",
4685:
4467:(1981), "How to make a digraph strongly connected",
1911:, with a yes or no answer (is it possible to remove
3532:Rosen, Edward M.; Henley, Ernest J. (Summer 1968),
2395:{\displaystyle {\tbinom {n}{2}}/2-\Omega (n^{3/2})}
1662:A weighted version of the problem can be solved in
4901:
3972:(1964), "A comment on minimum feedback arc sets",
3636:
3600:
3403:
3401:
2855:
2827:
2807:
2779:
2757:
2696:
2676:
2645:
2623:
2601:
2581:
2556:
2476:
2394:
2307:
2261:
2211:
2176:
2144:
2114:
2012:
1967:
1945:
1923:
1814:
1776:
1716:
1692:
1652:
1573:
1545:
1517:
1459:
1402:
1378:
1324:
1282:
1262:
1222:
1185:
1092:
1066:
1024:
992:
970:
908:
884:
862:
840:
774:
752:
715:
659:
608:
572:
517:
485:
465:
443:
419:
397:
375:
346:
4745:
3470:A study of asynchronous logical feedback networks
1290:vertices, this produces an acyclic subgraph with
5590:
4357:
1836:polytope associated with their feedback arc sets
1597:to the problem of contracting a set of edges (a
1460:{\displaystyle m/2+\Omega (m/{\sqrt {\Delta }})}
4513:
3407:
3398:
3277:Journal of the American Statistical Association
1120:
3327:
2960:
2557:{\displaystyle {\tbinom {n}{2}}/2-1.73n^{3/2}}
784:the feedback arc set problem can be solved in
5192:
5081:(2002), "The importance of being biased", in
4679:
4264:
4223:
4221:
4219:
3489:
2515:
2502:
2477:{\displaystyle {\tbinom {n}{2}}/2-O(n^{3/2})}
2429:
2416:
2347:
2334:
2032:; its NP-completeness was proved by Karp and
669:also using an exponential amount of space. A
5446:
5248:(1976), "On two minimax theorems in graph",
5132:; Manokaran, Rajsekar; Raghavendra, Prasad;
4829:
4648:
4642:
3772:
3377:(Fall 1959), "Mathematics without numbers",
2212:{\displaystyle {\tfrac {7}{6}}-\varepsilon }
2115:{\displaystyle {\tfrac {1}{2}}+\varepsilon }
1467:edges, giving an approximation ratio of the
1379:{\displaystyle {\tfrac {1}{2}}+\Omega (n/m)}
5285:
4558:, IEEE Computer Society, pp. 449–458,
3531:
3059:Journal of the Operational Research Society
177:men's beach volleyball at the 2016 Olympics
5073:
5022:
4516:Journal of the London Mathematical Society
4397:Approximating the maximum acyclic subgraph
4316:
4216:
3722:
3720:
2863:edges, and some graphs require this many.
1126:Does the feedback arc set problem have an
132:result that can be strengthened under the
96:, ranking competitors in sporting events,
5520:
5502:
5447:Isaak, Garth; Narayan, Darren A. (2004),
5384:
5263:
5206:
5052:
4390:
4388:
4200:
4104:
4027:
3900:
3857:
3827:
3742:
3424:
3415:; Chwa, Kyung-Yong; Park, Kunsoo (eds.),
3343:
3165:
2262:{\displaystyle O(2^{n^{1-\varepsilon }})}
1235:Fix an arbitrary ordering of the vertices
5491:Combinatorics, Probability and Computing
4911:Combinatorics, Probability and Computing
4546:
4544:
4459:
4457:
4419:
4417:
4242:A compendium of NP optimization problems
4144:
3998:
3996:
3807:
3805:
3639:ACM Journal of Experimental Algorithmics
3463:
3461:
3197:
3191:
3137:
2912:
2910:
2908:
1889:
496:
170:
31:
5325:
5319:
4957:Journal of Computer and System Sciences
4509:
4507:
4149:(1989), "Fair edge deletion problems",
3942:
3936:
3896:
3894:
3726:
3717:
3663:
3661:
3659:
3131:
3012:
2889:Fédération Internationale de Volleyball
1873:the resulting algorithm using walks on
1241:Return the larger of the two subgraphs.
1134:(more unsolved problems in mathematics)
14:
5614:Computational problems in graph theory
5591:
5244:
5238:
4394:
4385:
4087:
3968:
3962:
3766:
3558:
3373:
3367:
3237:
3231:
3052:"Properties of sports ranking methods"
3006:
2956:
2954:
2952:
2916:
546:of its strongly connected components.
5478:
5400:
5118:
4944:
4739:
4595:
4550:
4541:
4463:
4454:
4423:
4414:
4051:
3993:
3903:Journal of Combinatorial Optimization
3811:
3802:
3483:
3467:
3458:
3273:
3267:
2905:
5485:Huang, Hao; Ma, Jie; Shapira, Asaf;
5440:
5364:
5293:SIAM Journal on Discrete Mathematics
5279:
5186:
5016:
4989:
4983:
4869:SIAM Journal on Discrete Mathematics
4862:
4856:
4823:
4811:
4805:
4504:
4351:
4310:
4268:; Lin, Xuemin; Smyth, W. F. (1993),
4178:
4138:
3891:
3851:
3656:
3630:
3594:
3525:
3468:Unger, Stephen H. (April 26, 1957),
3321:
2047:
1855:polynomial-time approximation scheme
1584:
1186:{\displaystyle O(\log n\log \log n)}
1130:with a constant approximation ratio?
841:{\displaystyle O(n^{4}4^{k}k^{3}k!)}
716:{\displaystyle O(4^{n}/{\sqrt {n}})}
626:can find the optimal permutation in
334:A feedback arc set of a given graph
29:Edges that hit all cycles in a graph
5544:
4895:
4817:Complexity of Computer Computations
4258:
3975:IEEE Transactions on Circuit Theory
3945:IEEE Transactions on Circuit Theory
3862:, vol. 4, pp. 1863–1866,
3043:
2949:
2873:
2653:is itself an (acyclic) tournament.
1412:and finds an acyclic subgraph with
971:{\displaystyle O(2^{r}m^{4}\log m)}
429:and an edge for each two-edge path
64:of the given graph, often called a
24:
3607:Drawing Graphs: Methods and Models
3084:
2936:10.1111/j.2044-8317.1976.tb00701.x
2506:
2490:tournaments, the size is at least
2420:
2404:and some tournaments require size
2365:
2338:
2078:computational hardness assumptions
1593:, the feedback arc set problem is
1534:
1507:
1491:
1449:
1433:
1397:
1356:
25:
5625:
3331:Annals of Mathematical Statistics
2758:{\displaystyle (m^{2}+mn)/2n^{2}}
2177:{\displaystyle \varepsilon >0}
2145:{\displaystyle \varepsilon >0}
1777:{\displaystyle O(n^{5/2}\log nN)}
3174:Applied Animal Behaviour Science
1903:In order to apply the theory of
1653:{\displaystyle O(n^{5/2}\log n)}
1245:This can be improved by using a
205:group tournament ranking systems
5373:Journal of Combinatorial Theory
5331:Periodica Mathematica Hungarica
5251:Journal of Combinatorial Theory
5176:from the original on 2021-07-31
5064:from the original on 2009-09-20
5006:from the original on 2010-12-29
4866:(2006), "Ranking tournaments",
4795:from the original on 2021-08-03
4300:from the original on 2020-10-22
4248:from the original on 2021-07-29
3548:from the original on 2021-08-02
3202:, CRC Press, pp. 120–126,
2895:from the original on 2016-12-23
1223:{\displaystyle {\tfrac {1}{2}}}
1121:Unsolved problem in mathematics
321:
166:
147:A closely related problem, the
5453:Information Processing Letters
4360:Information Processing Letters
4274:Information Processing Letters
4152:IEEE Transactions on Computers
3538:Chemical Engineering Education
3097:ACM Transactions on Algorithms
2734:
2712:
2471:
2450:
2389:
2368:
2256:
2230:
2000:
1996:
1990:
1983:
1885:
1771:
1738:
1687:
1674:
1647:
1617:
1601:) to make the resulting graph
1512:
1494:
1454:
1436:
1373:
1359:
1180:
1153:
1114:
1061:
1046:
965:
933:
835:
796:
710:
685:
654:
638:
603:
594:
199:In sporting competitions with
112:; it can be solved exactly in
13:
1:
4843:, W.H. Freeman, p. 192,
4395:Newman, Alantha (June 2000),
4202:10.1016/S0166-218X(00)00339-5
3789:10.1016/S0166-218X(03)00444-X
3152:10.1016/s0003-3472(76)80022-x
2866:
2318:Every tournament graph has a
1867:linear programming relaxation
503:strongly connected components
316:
231:maximum likelihood estimation
76:; weighted versions of these
5562:10.1007/978-3-642-45043-3_26
5427:10.1016/0166-218X(94)00042-C
5414:Discrete Applied Mathematics
5386:10.1016/0095-8956(83)90060-6
5265:10.1016/0095-8956(76)90049-6
4970:10.1016/0022-0000(80)90046-X
4666:10.1016/0196-6774(88)90022-3
4372:10.1016/0020-0190(94)00086-7
4286:10.1016/0020-0190(93)90079-O
4188:Discrete Applied Mathematics
3776:Discrete Applied Mathematics
3186:10.1016/0168-1591(93)90137-e
671:divide-and-conquer algorithm
535:strongly connected component
501:A directed graph with three
7:
5054:10.4007/annals.2005.162.439
4115:10.1007/978-3-030-00256-5_6
4008:Theory of Computing Systems
3815:Theory of Computing Systems
3435:10.1007/978-3-642-17517-6_3
2156:exponential time hypothesis
1880:
1078:exponential time hypothesis
405:has a vertex for each edge
10:
5630:
4238:"Minimum Feedback Arc Set"
1553:, the approximation ratio
1080:, no better dependence on
1067:{\displaystyle O(t\log t)}
5513:10.1017/S0963548313000394
5465:10.1016/j.ipl.2004.07.001
5217:10.1007/s00236-016-0281-2
5146:SIAM Journal on Computing
5072:; preliminary version in
4923:10.1017/S0963548306007887
4728:author's extended version
4020:10.1007/s00224-011-9312-0
3868:10.1109/iscas.1992.230449
3838:10.1007/s00224-017-9777-6
3254:10.1093/biomet/48.3-4.303
3071:10.1057/s41274-017-0266-8
2977:10.1093/biomet/53.1-2.143
2273:
1896:NP-completeness reduction
1546:{\displaystyle \Delta =3}
870:in this algorithm is the
660:{\displaystyle O(n2^{n})}
250:exploratory data analysis
118:fixed-parameter tractable
72:and its removal leaves a
4760:Mathematical Programming
4608:Mathematical Programming
4564:10.1109/SFCS.1993.366842
4528:10.1112/jlms/s2-17.3.369
3988:10.1109/tct.1964.1082291
3957:10.1109/tct.1963.1082116
3208:10.1201/9780429049262-18
2656:A directed graph has an
2158:is true, then for every
2013:{\displaystyle |E(G)|-k}
1693:{\displaystyle O(n^{3})}
734:parameterized complexity
549:
74:maximum acyclic subgraph
70:minimum feedback arc set
18:Minimum feedback arc set
4753:; Kaplan, Haim (2002),
4707:10.1145/1250790.1250806
4410:Guruswami et al. (2011)
4074:10.1145/1411509.1411511
3915:10.1023/A:1009802905533
3615:10.1007/3-540-44969-8_5
3565:Di Battista, Giuseppe;
3534:"The New Stoichiometry"
3345:10.1214/aoms/1177703572
3316:2027/mdp.39015095254010
3110:10.1145/1798596.1798608
3029:10.1287/mnsc.29.12.1384
2308:{\displaystyle K_{3,3}}
2082:unique games conjecture
2030:21 NP-complete problems
2020:edges. This problem is
1869:of the problem, and to
1828:weakly acyclic digraphs
1815:{\displaystyle K_{3,3}}
1403:{\displaystyle \Delta }
1325:{\displaystyle m/2+n/6}
1128:approximation algorithm
760:vertices, with natural
544:triconnected components
331:sizes from each other.
227:mathematical psychology
134:unique games conjecture
98:mathematical psychology
4687:Kenyon-Mathieu, Claire
4441:10.1006/jagm.1995.1022
4338:10.1006/jagm.1997.0864
2857:
2829:
2809:
2781:
2759:
2698:
2678:
2647:
2625:
2603:
2583:
2568:directed acyclic graph
2558:
2478:
2396:
2309:
2263:
2213:
2178:
2146:
2116:
2014:
1969:
1947:
1925:
1900:
1816:
1778:
1718:
1694:
1654:
1575:
1547:
1519:
1461:
1404:
1380:
1326:
1284:
1264:
1224:
1187:
1094:
1068:
1026:
994:
972:
910:
886:
864:
842:
776:
754:
717:
661:
610:
574:
539:biconnected components
530:
527:biconnected components
519:
487:
467:
445:
421:
399:
377:
348:
290:, breaking edges of a
214:and more generally in
189:directed acyclic graph
180:
66:directed acyclic graph
37:
5126:Guruswami, Venkatesan
5095:10.1145/509907.509915
5040:Annals of Mathematics
4837:(1979), "A1.1: GT8",
4773:10.1007/s101070100271
4654:Journal of Algorithms
4429:Journal of Algorithms
4326:Journal of Algorithms
3744:10.1145/322344.322351
2858:
2830:
2810:
2782:
2760:
2699:
2679:
2648:
2626:
2604:
2584:
2559:
2479:
2397:
2310:
2264:
2214:
2179:
2147:
2117:
2052:The complexity class
2015:
1970:
1948:
1926:
1893:
1843:reducible flow graphs
1817:
1779:
1719:
1695:
1655:
1576:
1548:
1520:
1462:
1405:
1381:
1327:
1285:
1265:
1225:
1188:
1095:
1069:
1027:
995:
973:
911:
887:
865:
843:
777:
755:
718:
662:
611:
609:{\displaystyle O(n!)}
575:
520:
500:
488:
468:
446:
422:
400:
378:
349:
300:layered graph drawing
220:dominance hierarchies
174:
78:optimization problems
35:
5609:NP-complete problems
5604:Graph theory objects
4990:Kann, Viggo (1992),
4650:Ramachandran, Vijaya
3581:, pp. 265–302,
3512:10.1364/ao.34.008125
2839:
2819:
2791:
2771:
2709:
2688:
2668:
2637:
2615:
2593:
2573:
2495:
2409:
2327:
2286:
2224:
2188:
2162:
2130:
2091:
2038:vertex cover problem
1979:
1959:
1937:
1915:
1793:
1732:
1708:
1668:
1611:
1557:
1531:
1473:
1416:
1394:
1338:
1294:
1274:
1254:
1205:
1147:
1084:
1040:
1016:
984:
927:
900:
876:
854:
790:
766:
744:
679:
632:
622:method based on the
588:
564:
509:
477:
457:
435:
411:
389:
367:
338:
292:process flow diagram
288:chemical engineering
284:process flowsheeting
275:synchronous circuits
86:chemical engineering
4701:, pp. 95–103,
4004:Bodlaender, Hans L.
3504:1995ApOpt..34.8125F
3104:(3): A55:1–A55:13,
2856:{\displaystyle m/3}
2808:{\displaystyle n/3}
2058:approximation ratio
2028:'s original set of
1863:randomized rounding
1574:{\displaystyle 8/9}
1141:approximation ratio
624:Held–Karp algorithm
620:dynamic programming
356:feedback vertex set
280:combinational logic
261:Kemeny–Young method
149:feedback vertex set
126:approximation ratio
5522:20.500.11850/73894
5343:10.1007/BF02017965
5089:, pp. 33–42,
4733:2009-01-15 at the
4621:10.1007/BF01582009
4483:10.1007/BF02579270
4234:Woeginger, Gerhard
4061:Journal of the ACM
3730:Journal of the ACM
3696:10.1007/PL00009191
3016:Management Science
2853:
2825:
2805:
2777:
2755:
2694:
2674:
2662:strongly connected
2643:
2621:
2599:
2579:
2554:
2520:
2474:
2434:
2392:
2352:
2305:
2259:
2209:
2201:
2174:
2142:
2112:
2104:
2010:
1965:
1943:
1921:
1901:
1812:
1774:
1714:
1690:
1650:
1603:strongly connected
1571:
1543:
1515:
1486:
1457:
1400:
1376:
1351:
1322:
1280:
1260:
1220:
1218:
1183:
1090:
1064:
1022:
990:
968:
906:
882:
860:
838:
772:
750:
713:
657:
606:
570:
531:
515:
483:
463:
441:
417:
395:
373:
344:
181:
38:
5571:978-3-642-45042-6
5159:10.1137/090756144
4882:10.1137/050623905
4835:Johnson, David S.
4831:Garey, Michael R.
4691:Johnson, David S.
4603:Grötschel, Martin
4518:, Second Series,
4124:978-3-030-00255-8
3624:978-3-540-42062-0
3588:978-0-13-301615-4
3571:Tamassia, Roberto
3498:(35): 8125–8136,
3444:978-3-642-17516-9
3217:978-0-429-04926-2
3023:(12): 1384–1392,
2881:"Main draw – Men"
2828:{\displaystyle m}
2780:{\displaystyle n}
2697:{\displaystyle n}
2677:{\displaystyle m}
2646:{\displaystyle D}
2624:{\displaystyle D}
2602:{\displaystyle D}
2582:{\displaystyle D}
2513:
2427:
2345:
2200:
2103:
2048:Inapproximability
1968:{\displaystyle k}
1946:{\displaystyle k}
1924:{\displaystyle k}
1830:, defined by the
1717:{\displaystyle N}
1585:Restricted inputs
1581:can be achieved.
1510:
1485:
1452:
1350:
1283:{\displaystyle n}
1263:{\displaystyle m}
1217:
1093:{\displaystyle t}
1025:{\displaystyle t}
993:{\displaystyle r}
909:{\displaystyle k}
885:{\displaystyle 4}
863:{\displaystyle n}
775:{\displaystyle k}
753:{\displaystyle n}
738:natural parameter
708:
582:graph would take
573:{\displaystyle n}
518:{\displaystyle d}
486:{\displaystyle G}
466:{\displaystyle G}
444:{\displaystyle G}
420:{\displaystyle G}
398:{\displaystyle G}
376:{\displaystyle G}
354:is the same as a
347:{\displaystyle G}
311:operating systems
244:, the problem in
193:topological order
153:undirected graphs
138:tournament graphs
130:inapproximability
54:feedback edge set
16:(Redirected from
5621:
5583:
5582:
5548:
5542:
5541:
5524:
5506:
5482:
5476:
5475:
5444:
5438:
5437:
5409:Roberts, Fred S.
5404:
5398:
5397:
5388:
5368:
5362:
5361:
5323:
5317:
5316:
5286:Bar-Noy, Amotz;
5283:
5277:
5276:
5267:
5242:
5236:
5235:
5210:
5195:Acta Informatica
5190:
5184:
5183:
5182:
5181:
5175:
5142:
5122:
5116:
5115:
5071:
5070:
5069:
5063:
5056:
5036:
5020:
5014:
5013:
5012:
5011:
5005:
4998:
4987:
4981:
4980:
4948:
4942:
4941:
4908:
4899:
4893:
4892:
4860:
4854:
4853:
4827:
4821:
4820:
4813:Karp, Richard M.
4809:
4803:
4802:
4801:
4800:
4743:
4737:
4725:
4683:
4677:
4676:
4646:
4640:
4639:
4599:
4593:
4592:
4552:Gabow, Harold N.
4548:
4539:
4538:
4511:
4502:
4501:
4461:
4452:
4451:
4425:Gabow, Harold N.
4421:
4412:
4407:
4392:
4383:
4382:
4355:
4349:
4348:
4314:
4308:
4307:
4306:
4305:
4262:
4256:
4255:
4254:
4253:
4230:Karpinski, Marek
4225:
4214:
4213:
4204:
4195:(1–3): 253–265,
4182:
4176:
4175:
4165:10.1109/12.24280
4142:
4136:
4135:
4108:
4091:
4085:
4084:
4055:
4049:
4048:
4031:
4000:
3991:
3990:
3966:
3960:
3959:
3940:
3934:
3933:
3898:
3889:
3888:
3855:
3849:
3848:
3831:
3822:(5): 1048–1084,
3809:
3800:
3799:
3783:(2–3): 249–269,
3770:
3764:
3763:
3746:
3737:(4): 1023–1048,
3724:
3715:
3714:
3665:
3654:
3653:
3634:
3628:
3627:
3603:Wagner, Dorothea
3598:
3592:
3591:
3562:
3556:
3555:
3554:
3553:
3529:
3523:
3522:
3487:
3481:
3480:
3465:
3456:
3455:
3428:
3409:Karpinski, Marek
3405:
3396:
3395:
3371:
3365:
3364:
3347:
3325:
3319:
3318:
3308:
3284:(291): 503–520,
3271:
3265:
3264:
3248:(3–4): 303–312,
3235:
3229:
3228:
3195:
3189:
3188:
3169:
3163:
3162:
3140:Animal Behaviour
3135:
3129:
3128:
3092:Coppersmith, Don
3088:
3082:
3081:
3056:
3047:
3041:
3039:
3010:
3004:
3003:
2971:(1–2): 143–149,
2958:
2947:
2946:
2918:Hubert, Lawrence
2914:
2903:
2902:
2901:
2900:
2877:
2862:
2860:
2859:
2854:
2849:
2834:
2832:
2831:
2826:
2814:
2812:
2811:
2806:
2801:
2786:
2784:
2783:
2778:
2766:
2764:
2762:
2761:
2756:
2754:
2753:
2741:
2724:
2723:
2703:
2701:
2700:
2695:
2683:
2681:
2680:
2675:
2652:
2650:
2649:
2644:
2632:
2630:
2628:
2627:
2622:
2608:
2606:
2605:
2600:
2588:
2586:
2585:
2580:
2565:
2563:
2561:
2560:
2555:
2553:
2552:
2548:
2526:
2521:
2519:
2518:
2505:
2485:
2483:
2481:
2480:
2475:
2470:
2469:
2465:
2440:
2435:
2433:
2432:
2419:
2403:
2401:
2399:
2398:
2393:
2388:
2387:
2383:
2358:
2353:
2351:
2350:
2337:
2320:Hamiltonian path
2314:
2312:
2311:
2306:
2304:
2303:
2270:
2268:
2266:
2265:
2260:
2255:
2254:
2253:
2252:
2218:
2216:
2215:
2210:
2202:
2193:
2183:
2181:
2180:
2175:
2153:
2151:
2149:
2148:
2143:
2123:
2121:
2119:
2118:
2113:
2105:
2096:
2019:
2017:
2016:
2011:
2003:
1986:
1974:
1972:
1971:
1966:
1954:
1952:
1950:
1949:
1944:
1930:
1928:
1927:
1922:
1909:decision version
1821:
1819:
1818:
1813:
1811:
1810:
1785:
1783:
1781:
1780:
1775:
1758:
1757:
1753:
1725:
1723:
1721:
1720:
1715:
1701:
1699:
1697:
1696:
1691:
1686:
1685:
1661:
1659:
1657:
1656:
1651:
1637:
1636:
1632:
1580:
1578:
1577:
1572:
1567:
1552:
1550:
1549:
1544:
1526:
1524:
1522:
1521:
1516:
1511:
1506:
1504:
1487:
1478:
1466:
1464:
1463:
1458:
1453:
1448:
1446:
1426:
1411:
1409:
1407:
1406:
1401:
1387:
1385:
1383:
1382:
1377:
1369:
1352:
1343:
1331:
1329:
1328:
1323:
1318:
1304:
1289:
1287:
1286:
1281:
1269:
1267:
1266:
1261:
1247:greedy algorithm
1231:
1229:
1227:
1226:
1221:
1219:
1210:
1194:
1192:
1190:
1189:
1184:
1122:
1109:polynomial delay
1099:
1097:
1096:
1091:
1075:
1073:
1071:
1070:
1065:
1033:
1031:
1029:
1028:
1023:
999:
997:
996:
991:
979:
977:
975:
974:
969:
955:
954:
945:
944:
917:
915:
913:
912:
907:
893:
891:
889:
888:
883:
869:
867:
866:
861:
849:
847:
845:
844:
839:
828:
827:
818:
817:
808:
807:
783:
781:
779:
778:
773:
759:
757:
756:
751:
727:polynomial space
724:
722:
720:
719:
714:
709:
704:
702:
697:
696:
668:
666:
664:
663:
658:
653:
652:
617:
615:
613:
612:
607:
581:
579:
577:
576:
571:
524:
522:
521:
516:
492:
490:
489:
484:
472:
470:
469:
464:
452:
450:
448:
447:
442:
428:
426:
424:
423:
418:
404:
402:
401:
396:
384:
382:
380:
379:
374:
353:
351:
350:
345:
273:information. In
270:sequential logic
201:round-robin play
185:tournament graph
175:The scores from
114:exponential time
62:acyclic subgraph
50:feedback arc set
46:graph algorithms
21:
5629:
5628:
5624:
5623:
5622:
5620:
5619:
5618:
5599:Directed graphs
5589:
5588:
5587:
5586:
5572:
5549:
5545:
5483:
5479:
5445:
5441:
5405:
5401:
5369:
5365:
5324:
5320:
5306:10.1137/0403002
5284:
5280:
5243:
5239:
5191:
5187:
5179:
5177:
5173:
5140:
5134:Charikar, Moses
5123:
5119:
5105:
5067:
5065:
5061:
5034:
5021:
5017:
5009:
5007:
5003:
4996:
4988:
4984:
4949:
4945:
4906:
4900:
4896:
4861:
4857:
4851:
4828:
4824:
4810:
4806:
4798:
4796:
4744:
4740:
4735:Wayback Machine
4684:
4680:
4647:
4643:
4600:
4596:
4574:
4549:
4542:
4512:
4505:
4462:
4455:
4422:
4415:
4393:
4386:
4356:
4352:
4315:
4311:
4303:
4301:
4263:
4259:
4251:
4249:
4226:
4217:
4183:
4179:
4143:
4139:
4125:
4092:
4088:
4056:
4052:
4001:
3994:
3967:
3963:
3941:
3937:
3899:
3892:
3878:
3856:
3852:
3810:
3803:
3771:
3767:
3725:
3718:
3666:
3657:
3635:
3631:
3625:
3599:
3595:
3589:
3563:
3559:
3551:
3549:
3530:
3526:
3488:
3484:
3466:
3459:
3445:
3413:Cheong, Otfried
3406:
3399:
3375:Kemeny, John G.
3372:
3368:
3326:
3322:
3314:
3290:10.2307/2281911
3272:
3268:
3236:
3232:
3218:
3200:Insect Behavior
3196:
3192:
3170:
3166:
3136:
3132:
3089:
3085:
3054:
3048:
3044:
3011:
3007:
2959:
2950:
2915:
2906:
2898:
2896:
2879:
2878:
2874:
2869:
2845:
2840:
2837:
2836:
2820:
2817:
2816:
2797:
2792:
2789:
2788:
2772:
2769:
2768:
2749:
2745:
2737:
2719:
2715:
2710:
2707:
2706:
2705:
2689:
2686:
2685:
2669:
2666:
2665:
2660:whenever it is
2638:
2635:
2634:
2616:
2613:
2612:
2610:
2594:
2591:
2590:
2574:
2571:
2570:
2544:
2540:
2536:
2522:
2514:
2501:
2500:
2498:
2496:
2493:
2492:
2491:
2461:
2457:
2453:
2436:
2428:
2415:
2414:
2412:
2410:
2407:
2406:
2405:
2379:
2375:
2371:
2354:
2346:
2333:
2332:
2330:
2328:
2325:
2324:
2323:
2293:
2289:
2287:
2284:
2283:
2280:min-max theorem
2276:
2242:
2238:
2237:
2233:
2225:
2222:
2221:
2220:
2191:
2189:
2186:
2185:
2163:
2160:
2159:
2131:
2128:
2127:
2125:
2094:
2092:
2089:
2088:
2086:
2050:
2026:Richard M. Karp
1999:
1982:
1980:
1977:
1976:
1960:
1957:
1956:
1938:
1935:
1934:
1932:
1916:
1913:
1912:
1905:NP-completeness
1888:
1883:
1875:expander graphs
1800:
1796:
1794:
1791:
1790:
1749:
1745:
1741:
1733:
1730:
1729:
1727:
1709:
1706:
1705:
1703:
1681:
1677:
1669:
1666:
1665:
1663:
1628:
1624:
1620:
1612:
1609:
1608:
1606:
1587:
1563:
1558:
1555:
1554:
1532:
1529:
1528:
1505:
1500:
1476:
1474:
1471:
1470:
1468:
1447:
1442:
1422:
1417:
1414:
1413:
1395:
1392:
1391:
1389:
1365:
1341:
1339:
1336:
1335:
1333:
1314:
1300:
1295:
1292:
1291:
1275:
1272:
1271:
1255:
1252:
1251:
1208:
1206:
1203:
1202:
1200:
1148:
1145:
1144:
1143:
1137:
1136:
1131:
1124:
1117:
1085:
1082:
1081:
1041:
1038:
1037:
1035:
1017:
1014:
1013:
1009:
985:
982:
981:
950:
946:
940:
936:
928:
925:
924:
922:
901:
898:
897:
895:
877:
874:
873:
871:
855:
852:
851:
823:
819:
813:
809:
803:
799:
791:
788:
787:
785:
767:
764:
763:
761:
745:
742:
741:
703:
698:
692:
688:
680:
677:
676:
674:
648:
644:
633:
630:
629:
627:
589:
586:
585:
583:
565:
562:
561:
560:
552:
510:
507:
506:
478:
475:
474:
458:
455:
454:
436:
433:
432:
430:
412:
409:
408:
406:
390:
387:
386:
368:
365:
364:
362:
339:
336:
335:
324:
319:
235:log-likelihoods
169:
122:polynomial time
30:
23:
22:
15:
12:
11:
5:
5627:
5617:
5616:
5611:
5606:
5601:
5585:
5584:
5570:
5543:
5497:(6): 859–873,
5487:Sudakov, Benny
5477:
5459:(3): 107–111,
5439:
5421:(1–3): 39–76,
5399:
5379:(3): 328–332,
5363:
5337:(2): 131–144,
5318:
5278:
5246:Lovász, László
5237:
5185:
5153:(3): 878–914,
5117:
5103:
5047:(1): 439–485,
5015:
4982:
4964:(1): 136–153,
4943:
4894:
4876:(1): 137–142,
4855:
4849:
4822:
4804:
4747:Arora, Sanjeev
4738:
4678:
4660:(3): 299–313,
4641:
4594:
4572:
4540:
4522:(3): 369–374,
4503:
4477:(2): 145–153,
4453:
4435:(3): 586–628,
4413:
4408:, as cited by
4384:
4366:(3): 133–140,
4350:
4322:Shor, Peter W.
4318:Berger, Bonnie
4309:
4280:(6): 319–323,
4257:
4215:
4177:
4159:(5): 756–761,
4137:
4123:
4086:
4050:
4014:(3): 420–432,
3992:
3982:(2): 296–297,
3961:
3951:(2): 238–245,
3935:
3909:(2): 235–251,
3890:
3876:
3850:
3801:
3765:
3716:
3690:(2): 151–174,
3655:
3629:
3623:
3593:
3587:
3557:
3544:(3): 120–125,
3524:
3492:Applied Optics
3482:
3457:
3443:
3397:
3387:(4): 577–591,
3366:
3338:(2): 739–747,
3320:
3266:
3230:
3216:
3190:
3180:(3): 199–213,
3164:
3146:(4): 917–938,
3130:
3083:
3065:(5): 776–787,
3042:
3005:
2948:
2904:
2871:
2870:
2868:
2865:
2852:
2848:
2844:
2824:
2804:
2800:
2796:
2776:
2752:
2748:
2744:
2740:
2736:
2733:
2730:
2727:
2722:
2718:
2714:
2693:
2673:
2642:
2620:
2598:
2578:
2551:
2547:
2543:
2539:
2535:
2532:
2529:
2525:
2517:
2512:
2509:
2504:
2473:
2468:
2464:
2460:
2456:
2452:
2449:
2446:
2443:
2439:
2431:
2426:
2423:
2418:
2391:
2386:
2382:
2378:
2374:
2370:
2367:
2364:
2361:
2357:
2349:
2344:
2341:
2336:
2302:
2299:
2296:
2292:
2275:
2272:
2258:
2251:
2248:
2245:
2241:
2236:
2232:
2229:
2208:
2205:
2199:
2196:
2173:
2170:
2167:
2141:
2138:
2135:
2111:
2108:
2102:
2099:
2049:
2046:
2009:
2006:
2002:
1998:
1995:
1992:
1989:
1985:
1964:
1942:
1920:
1887:
1884:
1882:
1879:
1809:
1806:
1803:
1799:
1773:
1770:
1767:
1764:
1761:
1756:
1752:
1748:
1744:
1740:
1737:
1713:
1689:
1684:
1680:
1676:
1673:
1649:
1646:
1643:
1640:
1635:
1631:
1627:
1623:
1619:
1616:
1586:
1583:
1570:
1566:
1562:
1542:
1539:
1536:
1514:
1509:
1503:
1499:
1496:
1493:
1490:
1484:
1481:
1456:
1451:
1445:
1441:
1438:
1435:
1432:
1429:
1425:
1421:
1399:
1375:
1372:
1368:
1364:
1361:
1358:
1355:
1349:
1346:
1321:
1317:
1313:
1310:
1307:
1303:
1299:
1279:
1259:
1243:
1242:
1239:
1236:
1216:
1213:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1161:
1158:
1155:
1152:
1132:
1125:
1119:
1116:
1113:
1089:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1021:
989:
967:
964:
961:
958:
953:
949:
943:
939:
935:
932:
905:
881:
859:
837:
834:
831:
826:
822:
816:
812:
806:
802:
798:
795:
771:
749:
712:
707:
701:
695:
691:
687:
684:
656:
651:
647:
643:
640:
637:
605:
602:
599:
596:
593:
569:
551:
548:
514:
482:
462:
440:
416:
394:
372:
358:of a directed
343:
328:complement set
323:
320:
318:
315:
309:resolution in
266:
265:
253:
238:
223:
208:
168:
165:
157:spanning trees
58:directed graph
28:
9:
6:
4:
3:
2:
5626:
5615:
5612:
5610:
5607:
5605:
5602:
5600:
5597:
5596:
5594:
5581:
5577:
5573:
5567:
5563:
5559:
5555:
5547:
5540:
5536:
5532:
5528:
5523:
5518:
5514:
5510:
5505:
5500:
5496:
5492:
5488:
5481:
5474:
5470:
5466:
5462:
5458:
5454:
5450:
5443:
5436:
5432:
5428:
5424:
5420:
5416:
5415:
5410:
5403:
5396:
5392:
5387:
5382:
5378:
5374:
5367:
5360:
5356:
5352:
5348:
5344:
5340:
5336:
5332:
5328:
5322:
5315:
5311:
5307:
5303:
5299:
5295:
5294:
5289:
5282:
5275:
5271:
5266:
5261:
5258:(2): 96–103,
5257:
5253:
5252:
5247:
5241:
5234:
5230:
5226:
5222:
5218:
5214:
5209:
5204:
5200:
5196:
5189:
5172:
5168:
5164:
5160:
5156:
5152:
5148:
5147:
5139:
5135:
5131:
5130:Håstad, Johan
5127:
5121:
5114:
5110:
5106:
5104:1-58113-495-9
5100:
5096:
5092:
5088:
5084:
5083:Reif, John H.
5080:
5079:Safra, Samuel
5076:
5060:
5055:
5050:
5046:
5042:
5041:
5033:
5029:
5028:Safra, Samuel
5025:
5019:
5002:
4995:
4994:
4986:
4979:
4975:
4971:
4967:
4963:
4959:
4958:
4953:
4947:
4940:
4936:
4932:
4928:
4924:
4920:
4916:
4912:
4905:
4898:
4891:
4887:
4883:
4879:
4875:
4871:
4870:
4865:
4859:
4852:
4850:0-7167-1045-5
4846:
4842:
4841:
4836:
4832:
4826:
4818:
4814:
4808:
4794:
4790:
4786:
4782:
4778:
4774:
4770:
4766:
4762:
4761:
4756:
4752:
4748:
4742:
4736:
4732:
4729:
4724:
4720:
4716:
4712:
4708:
4704:
4700:
4696:
4692:
4688:
4682:
4675:
4671:
4667:
4663:
4659:
4655:
4651:
4645:
4638:
4634:
4630:
4626:
4622:
4618:
4614:
4610:
4609:
4604:
4598:
4591:
4587:
4583:
4579:
4575:
4573:0-8186-4370-6
4569:
4565:
4561:
4557:
4553:
4547:
4545:
4537:
4533:
4529:
4525:
4521:
4517:
4510:
4508:
4500:
4496:
4492:
4488:
4484:
4480:
4476:
4472:
4471:
4470:Combinatorica
4466:
4465:Frank, András
4460:
4458:
4450:
4446:
4442:
4438:
4434:
4430:
4426:
4420:
4418:
4411:
4406:
4402:
4398:
4391:
4389:
4381:
4377:
4373:
4369:
4365:
4361:
4354:
4347:
4343:
4339:
4335:
4331:
4327:
4323:
4319:
4313:
4299:
4295:
4291:
4287:
4283:
4279:
4275:
4271:
4267:
4261:
4247:
4243:
4239:
4235:
4231:
4224:
4222:
4220:
4212:
4208:
4203:
4198:
4194:
4190:
4189:
4181:
4174:
4170:
4166:
4162:
4158:
4154:
4153:
4148:
4147:Sahni, Sartaj
4145:Lin, Lishin;
4141:
4134:
4130:
4126:
4120:
4116:
4112:
4107:
4102:
4098:
4090:
4083:
4079:
4075:
4071:
4067:
4063:
4062:
4054:
4047:
4043:
4039:
4035:
4030:
4025:
4021:
4017:
4013:
4009:
4005:
3999:
3997:
3989:
3985:
3981:
3977:
3976:
3971:
3965:
3958:
3954:
3950:
3946:
3939:
3932:
3928:
3924:
3920:
3916:
3912:
3908:
3904:
3897:
3895:
3887:
3883:
3879:
3877:0-7803-0593-0
3873:
3869:
3865:
3861:
3854:
3847:
3843:
3839:
3835:
3830:
3825:
3821:
3817:
3816:
3808:
3806:
3798:
3794:
3790:
3786:
3782:
3778:
3777:
3769:
3762:
3758:
3754:
3750:
3745:
3740:
3736:
3732:
3731:
3723:
3721:
3713:
3709:
3705:
3701:
3697:
3693:
3689:
3685:
3684:
3679:
3675:
3671:
3664:
3662:
3660:
3652:
3648:
3644:
3640:
3633:
3626:
3620:
3616:
3612:
3608:
3604:
3597:
3590:
3584:
3580:
3579:Prentice Hall
3576:
3572:
3568:
3561:
3547:
3543:
3539:
3535:
3528:
3521:
3517:
3513:
3509:
3505:
3501:
3497:
3493:
3486:
3479:
3475:
3471:
3464:
3462:
3454:
3450:
3446:
3440:
3436:
3432:
3427:
3422:
3418:
3414:
3410:
3404:
3402:
3394:
3390:
3386:
3382:
3381:
3376:
3370:
3363:
3359:
3355:
3351:
3346:
3341:
3337:
3333:
3332:
3324:
3317:
3312:
3307:
3303:
3299:
3295:
3291:
3287:
3283:
3279:
3278:
3270:
3263:
3259:
3255:
3251:
3247:
3243:
3242:
3234:
3227:
3223:
3219:
3213:
3209:
3205:
3201:
3194:
3187:
3183:
3179:
3175:
3168:
3161:
3157:
3153:
3149:
3145:
3141:
3134:
3127:
3123:
3119:
3115:
3111:
3107:
3103:
3099:
3098:
3093:
3087:
3080:
3076:
3072:
3068:
3064:
3060:
3053:
3046:
3038:
3034:
3030:
3026:
3022:
3018:
3017:
3009:
3002:
2998:
2994:
2990:
2986:
2982:
2978:
2974:
2970:
2966:
2965:
2957:
2955:
2953:
2945:
2941:
2937:
2933:
2929:
2925:
2924:
2919:
2913:
2911:
2909:
2894:
2890:
2886:
2882:
2876:
2872:
2864:
2850:
2846:
2842:
2822:
2802:
2798:
2794:
2774:
2750:
2746:
2742:
2738:
2731:
2728:
2725:
2720:
2716:
2691:
2671:
2663:
2659:
2654:
2640:
2618:
2596:
2576:
2569:
2549:
2545:
2541:
2537:
2533:
2530:
2527:
2523:
2510:
2507:
2489:
2466:
2462:
2458:
2454:
2447:
2444:
2441:
2437:
2424:
2421:
2384:
2380:
2376:
2372:
2362:
2359:
2355:
2342:
2339:
2321:
2316:
2300:
2297:
2294:
2290:
2281:
2271:
2249:
2246:
2243:
2239:
2234:
2227:
2206:
2203:
2197:
2194:
2171:
2168:
2165:
2157:
2139:
2136:
2133:
2109:
2106:
2100:
2097:
2083:
2079:
2074:
2071:
2067:
2063:
2059:
2055:
2045:
2041:
2039:
2035:
2034:Eugene Lawler
2031:
2027:
2023:
2007:
2004:
1993:
1987:
1962:
1940:
1918:
1910:
1906:
1897:
1892:
1878:
1876:
1872:
1868:
1864:
1860:
1856:
1852:
1847:
1844:
1839:
1837:
1834:of a certain
1833:
1829:
1825:
1807:
1804:
1801:
1797:
1789:
1788:utility graph
1768:
1765:
1762:
1759:
1754:
1750:
1746:
1742:
1735:
1711:
1682:
1678:
1671:
1644:
1641:
1638:
1633:
1629:
1625:
1621:
1614:
1604:
1600:
1596:
1592:
1591:planar graphs
1582:
1568:
1564:
1560:
1540:
1537:
1501:
1497:
1488:
1482:
1479:
1443:
1439:
1430:
1427:
1423:
1419:
1370:
1366:
1362:
1353:
1347:
1344:
1319:
1315:
1311:
1308:
1305:
1301:
1297:
1277:
1257:
1248:
1240:
1237:
1234:
1233:
1232:
1214:
1211:
1197:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1150:
1142:
1135:
1129:
1112:
1110:
1106:
1101:
1100:is possible.
1087:
1079:
1058:
1055:
1052:
1049:
1043:
1019:
1012:
1007:
1006:spanning tree
1003:
987:
962:
959:
956:
951:
947:
941:
937:
930:
919:
903:
879:
857:
832:
829:
824:
820:
814:
810:
804:
800:
793:
769:
747:
739:
735:
730:
728:
705:
699:
693:
689:
682:
672:
649:
645:
641:
635:
625:
621:
600:
597:
591:
567:
558:
547:
545:
540:
536:
528:
512:
504:
499:
495:
480:
460:
438:
414:
392:
370:
361:
357:
341:
332:
329:
314:
312:
308:
303:
301:
296:
293:
289:
285:
281:
276:
271:
262:
258:
257:ranked voting
254:
251:
247:
243:
239:
236:
232:
228:
224:
221:
217:
213:
209:
206:
202:
198:
197:
196:
194:
191:whose unique
190:
186:
178:
173:
164:
162:
158:
154:
150:
145:
143:
142:planar graphs
139:
135:
131:
127:
123:
119:
115:
111:
107:
106:graph drawing
103:
99:
95:
94:ranked voting
91:
87:
82:
79:
75:
71:
67:
63:
59:
55:
51:
47:
43:
34:
27:
19:
5553:
5546:
5494:
5490:
5480:
5456:
5452:
5442:
5418:
5412:
5402:
5376:
5375:, Series B,
5372:
5366:
5334:
5330:
5321:
5297:
5291:
5288:Naor, Joseph
5281:
5255:
5254:, Series B,
5249:
5240:
5198:
5194:
5188:
5178:, retrieved
5150:
5144:
5120:
5086:
5066:, retrieved
5044:
5038:
5018:
5008:, retrieved
4992:
4985:
4961:
4955:
4952:Ausiello, G.
4946:
4914:
4910:
4897:
4873:
4867:
4858:
4839:
4825:
4816:
4807:
4797:, retrieved
4764:
4758:
4751:Frieze, Alan
4741:
4698:
4695:Feige, Uriel
4681:
4657:
4653:
4644:
4615:(1): 28–42,
4612:
4606:
4597:
4555:
4519:
4515:
4474:
4468:
4432:
4428:
4405:1721.1/86548
4396:
4363:
4359:
4353:
4329:
4325:
4312:
4302:, retrieved
4277:
4273:
4266:Eades, Peter
4260:
4250:, retrieved
4241:
4192:
4186:
4180:
4156:
4150:
4140:
4096:
4089:
4065:
4059:
4053:
4011:
4007:
3979:
3973:
3964:
3948:
3944:
3938:
3906:
3902:
3859:
3853:
3819:
3813:
3780:
3774:
3768:
3734:
3728:
3687:
3683:Algorithmica
3681:
3674:Schieber, B.
3642:
3638:
3632:
3606:
3596:
3574:
3567:Eades, Peter
3560:
3550:, retrieved
3541:
3537:
3527:
3495:
3491:
3485:
3469:
3416:
3384:
3378:
3369:
3335:
3329:
3323:
3281:
3275:
3269:
3245:
3239:
3233:
3199:
3193:
3177:
3173:
3167:
3143:
3139:
3133:
3101:
3095:
3086:
3062:
3058:
3045:
3020:
3014:
3008:
2968:
2962:
2930:(1): 32–52,
2927:
2921:
2897:, retrieved
2884:
2875:
2655:
2317:
2277:
2075:
2051:
2042:
1902:
1859:dense graphs
1848:
1840:
1827:
1589:In directed
1588:
1244:
1198:
1138:
1102:
1002:circuit rank
920:
894:independent
737:
731:
557:permutations
553:
532:
333:
325:
322:Equivalences
304:
297:
267:
182:
167:Applications
161:circuit rank
146:
92:resolution,
83:
73:
69:
61:
53:
49:
42:graph theory
39:
26:
5327:Spencer, J.
5300:(1): 7–20,
5201:(1): 1–15,
5075:Dinur, Irit
5024:Dinur, Irit
4767:(1): 1–36,
4726:; see also
4332:(1): 1–18,
4068:(5): 1–19,
3645:: 171–182,
3478:1721.1/4763
2022:NP-complete
1886:NP-hardness
1871:derandomize
1853:, it has a
1851:tournaments
1832:integrality
1824:graph minor
1115:Approximate
1105:linear time
212:primatology
5593:Categories
5180:2021-07-31
5068:2021-07-29
5010:2007-10-11
4917:(1): 1–4,
4864:Alon, Noga
4799:2021-08-03
4304:2021-08-01
4252:2021-07-29
4106:1707.01470
3970:Lawler, E.
3829:1702.07612
3668:Even, G.;
3552:2021-08-02
3241:Biometrika
2964:Biometrika
2899:2021-11-14
2867:References
2684:edges and
2658:Euler tour
2488:almost all
1270:edges and
1076:Under the
762:parameter
360:line graph
317:Algorithms
246:statistics
5504:1202.2602
5359:119894999
5208:1402.2843
4637:206798683
4029:1956/4556
3931:207632524
3886:122603659
3678:Sudan, M.
3426:1006.4396
3226:203898549
2531:−
2445:−
2366:Ω
2363:−
2250:ε
2247:−
2207:ε
2204:−
2166:ε
2134:ε
2110:ε
2070:reduction
2005:−
1763:
1642:
1535:Δ
1508:Δ
1492:Ω
1450:Δ
1434:Ω
1398:Δ
1357:Ω
1175:
1169:
1160:
1111:per set.
1056:
1011:treewidth
960:
872:constant
525:into two
242:seriation
120:time. In
5171:archived
5136:(2011),
5059:archived
5030:(2005),
5001:archived
4939:36539840
4793:archived
4731:Archived
4723:TR06-144
4697:(eds.),
4590:32162097
4499:27825518
4298:archived
4246:archived
4236:(2000),
3846:18394348
3670:Naor, J.
3605:(eds.),
3546:archived
3520:21068927
3453:16512997
3393:20026529
3380:Daedalus
3160:54284406
3079:51887586
2893:archived
2885:Rio 2016
2062:APX-hard
1881:Hardness
307:deadlock
216:ethology
116:, or in
102:ethology
90:deadlock
5580:3139198
5539:7967738
5531:3111546
5473:2095357
5435:1339075
5395:0735201
5351:0573525
5314:1033709
5274:0427138
5233:3136275
5225:3757549
5167:2823511
5113:1235048
5085:(ed.),
4978:0589808
4931:2282830
4890:2257251
4789:3207086
4781:1892295
4715:9436948
4674:0955140
4629:0809747
4582:1328441
4536:0500618
4491:0625547
4449:1334365
4380:1290207
4346:1474592
4294:1256786
4211:1881280
4173:0994519
4133:8008855
4082:1547510
4046:9967521
4038:2885638
3923:1772828
3797:2045215
3761:5284738
3753:0674256
3712:2437790
3704:1484534
3651:2027115
3500:Bibcode
3362:0161419
3354:2238526
3306:0115242
3298:2281911
3262:2332752
3118:2682624
3037:0809110
3001:5964054
2993:0196854
2985:2334060
2944:0429180
1933:number
1704:number
1390:degree
1000:is the
580:-vertex
110:NP-hard
5578:
5568:
5537:
5529:
5471:
5433:
5393:
5357:
5349:
5312:
5272:
5231:
5223:
5165:
5111:
5101:
4976:
4937:
4929:
4888:
4847:
4787:
4779:
4721:
4713:
4672:
4635:
4627:
4588:
4580:
4570:
4534:
4497:
4489:
4447:
4378:
4344:
4292:
4209:
4171:
4131:
4121:
4080:
4044:
4036:
3929:
3921:
3884:
3874:
3844:
3795:
3759:
3751:
3710:
3702:
3649:
3621:
3585:
3518:
3451:
3441:
3391:
3360:
3352:
3304:
3296:
3260:
3224:
3214:
3158:
3124:
3116:
3077:
3035:
2999:
2991:
2983:
2942:
2566:Every
2274:Theory
2126:every
2066:P = NP
1599:dijoin
980:where
725:using
618:but a
559:of an
259:, the
155:, the
136:. For
104:, and
5535:S2CID
5499:arXiv
5355:S2CID
5229:S2CID
5203:arXiv
5174:(PDF)
5141:(PDF)
5109:S2CID
5062:(PDF)
5035:(PDF)
5004:(PDF)
4997:(PDF)
4935:S2CID
4907:(PDF)
4785:S2CID
4711:S2CID
4633:S2CID
4586:S2CID
4495:S2CID
4129:S2CID
4101:arXiv
4078:S2CID
4042:S2CID
3927:S2CID
3882:S2CID
3842:S2CID
3824:arXiv
3757:S2CID
3708:S2CID
3449:S2CID
3421:arXiv
3389:JSTOR
3350:JSTOR
3294:JSTOR
3258:JSTOR
3222:S2CID
3156:S2CID
3126:18416
3122:S2CID
3075:S2CID
3055:(PDF)
2981:JSTOR
1865:to a
1822:as a
1728:time
1664:time
1607:time
1527:When
1469:form
923:time
786:time
675:time
628:time
584:time
550:Exact
56:in a
5566:ISBN
5099:ISBN
4845:ISBN
4719:ECCC
4568:ISBN
4119:ISBN
3872:ISBN
3619:ISBN
3583:ISBN
3516:PMID
3439:ISBN
3212:ISBN
2997:PMID
2534:1.73
2486:For
2169:>
2137:>
2124:for
1894:The
1841:The
1595:dual
248:and
48:, a
44:and
5558:doi
5517:hdl
5509:doi
5461:doi
5423:doi
5381:doi
5339:doi
5302:doi
5260:doi
5213:doi
5155:doi
5091:doi
5049:doi
5045:162
4966:doi
4919:doi
4878:doi
4769:doi
4703:doi
4662:doi
4617:doi
4560:doi
4524:doi
4479:doi
4437:doi
4401:hdl
4368:doi
4334:doi
4282:doi
4197:doi
4193:117
4161:doi
4111:doi
4070:doi
4024:hdl
4016:doi
3984:doi
3953:doi
3911:doi
3864:doi
3834:doi
3785:doi
3781:136
3739:doi
3692:doi
3611:doi
3508:doi
3474:hdl
3431:doi
3340:doi
3311:hdl
3286:doi
3250:doi
3204:doi
3182:doi
3148:doi
3106:doi
3067:doi
3025:doi
2973:doi
2932:doi
2611:of
2087:of
2054:APX
1760:log
1726:in
1639:log
1334:of
1201:of
1172:log
1166:log
1157:log
1053:log
1036:in
957:log
896:of
732:In
431:in
407:of
363:of
305:In
298:In
286:in
255:In
225:In
210:In
52:or
40:In
5595::
5576:MR
5574:,
5564:,
5533:,
5527:MR
5525:,
5515:,
5507:,
5495:22
5493:,
5469:MR
5467:,
5457:92
5455:,
5451:,
5431:MR
5429:,
5419:60
5417:,
5391:MR
5389:,
5377:35
5353:,
5347:MR
5345:,
5335:11
5333:,
5310:MR
5308:,
5296:,
5270:MR
5268:,
5256:21
5227:,
5221:MR
5219:,
5211:,
5199:55
5197:,
5169:,
5163:MR
5161:,
5151:40
5149:,
5143:,
5128:;
5107:,
5097:,
5077:;
5057:,
5043:,
5037:,
5026:;
4974:MR
4972:,
4962:21
4960:,
4933:,
4927:MR
4925:,
4915:16
4913:,
4909:,
4886:MR
4884:,
4874:20
4872:,
4833:;
4791:,
4783:,
4777:MR
4775:,
4765:92
4763:,
4757:,
4749:;
4717:,
4709:,
4693:;
4670:MR
4668:,
4656:,
4631:,
4625:MR
4623:,
4613:33
4611:,
4584:,
4578:MR
4576:,
4566:,
4543:^
4532:MR
4530:,
4520:17
4506:^
4493:,
4487:MR
4485:,
4473:,
4456:^
4445:MR
4443:,
4433:18
4431:,
4416:^
4387:^
4376:MR
4374:,
4364:51
4362:,
4342:MR
4340:,
4330:25
4328:,
4320:;
4296:,
4290:MR
4288:,
4278:47
4276:,
4272:,
4244:,
4240:,
4232:;
4218:^
4207:MR
4205:,
4191:,
4169:MR
4167:,
4157:38
4155:,
4127:,
4117:,
4109:,
4076:,
4066:55
4064:,
4040:,
4034:MR
4032:,
4022:,
4012:50
4010:,
3995:^
3980:11
3978:,
3949:10
3947:,
3925:,
3919:MR
3917:,
3905:,
3893:^
3880:,
3870:,
3840:,
3832:,
3820:62
3818:,
3804:^
3793:MR
3791:,
3779:,
3755:,
3749:MR
3747:,
3735:29
3733:,
3719:^
3706:,
3700:MR
3698:,
3688:20
3686:,
3676:;
3672:;
3658:^
3647:MR
3641:,
3617:,
3577:,
3569:;
3540:,
3536:,
3514:,
3506:,
3496:34
3494:,
3460:^
3447:,
3437:,
3429:,
3400:^
3385:88
3383:,
3358:MR
3356:,
3348:,
3336:35
3334:,
3302:MR
3300:,
3292:,
3282:55
3280:,
3256:,
3246:48
3244:,
3220:,
3210:,
3178:35
3176:,
3154:,
3144:24
3142:,
3120:,
3114:MR
3112:,
3100:,
3073:,
3063:69
3061:,
3057:,
3033:MR
3031:,
3021:29
3019:,
2995:,
2989:MR
2987:,
2979:,
2969:53
2967:,
2951:^
2940:MR
2938:,
2928:29
2926:,
2907:^
2891:,
2887:,
2883:,
1877:.
729:.
218:,
163:.
100:,
88:,
5560::
5519::
5511::
5501::
5463::
5425::
5383::
5341::
5304::
5298:3
5262::
5215::
5205::
5157::
5093::
5051::
4968::
4921::
4880::
4771::
4705::
4664::
4658:9
4619::
4562::
4526::
4481::
4475:1
4439::
4403::
4370::
4336::
4284::
4199::
4163::
4113::
4103::
4072::
4026::
4018::
3986::
3955::
3913::
3907:4
3866::
3836::
3826::
3787::
3741::
3694::
3643:6
3613::
3542:2
3510::
3502::
3476::
3433::
3423::
3342::
3313::
3288::
3252::
3206::
3184::
3150::
3108::
3102:6
3069::
3027::
2975::
2934::
2851:3
2847:/
2843:m
2823:m
2803:3
2799:/
2795:n
2775:n
2765:.
2751:2
2747:n
2743:2
2739:/
2735:)
2732:n
2729:m
2726:+
2721:2
2717:m
2713:(
2692:n
2672:m
2641:D
2631:,
2619:D
2597:D
2577:D
2564:.
2550:2
2546:/
2542:3
2538:n
2528:2
2524:/
2516:)
2511:2
2508:n
2503:(
2484:.
2472:)
2467:2
2463:/
2459:3
2455:n
2451:(
2448:O
2442:2
2438:/
2430:)
2425:2
2422:n
2417:(
2402:,
2390:)
2385:2
2381:/
2377:3
2373:n
2369:(
2360:2
2356:/
2348:)
2343:2
2340:n
2335:(
2301:3
2298:,
2295:3
2291:K
2269:.
2257:)
2244:1
2240:n
2235:2
2231:(
2228:O
2198:6
2195:7
2172:0
2152:.
2140:0
2122:,
2107:+
2101:2
2098:1
2008:k
2001:|
1997:)
1994:G
1991:(
1988:E
1984:|
1963:k
1953:.
1941:k
1919:k
1808:3
1805:,
1802:3
1798:K
1784:.
1772:)
1769:N
1766:n
1755:2
1751:/
1747:5
1743:n
1739:(
1736:O
1724:,
1712:N
1700:,
1688:)
1683:3
1679:n
1675:(
1672:O
1660:.
1648:)
1645:n
1634:2
1630:/
1626:5
1622:n
1618:(
1615:O
1569:9
1565:/
1561:8
1541:3
1538:=
1525:.
1513:)
1502:/
1498:1
1495:(
1489:+
1483:2
1480:1
1455:)
1444:/
1440:m
1437:(
1431:+
1428:2
1424:/
1420:m
1410:,
1386:.
1374:)
1371:m
1367:/
1363:n
1360:(
1354:+
1348:2
1345:1
1320:6
1316:/
1312:n
1309:+
1306:2
1302:/
1298:m
1278:n
1258:m
1230::
1215:2
1212:1
1193:.
1181:)
1178:n
1163:n
1154:(
1151:O
1123::
1088:t
1074:.
1062:)
1059:t
1050:t
1047:(
1044:O
1032:,
1020:t
988:r
978:,
966:)
963:m
952:4
948:m
942:r
938:2
934:(
931:O
916:,
904:k
892:,
880:4
858:n
848:,
836:)
833:!
830:k
825:3
821:k
815:k
811:4
805:4
801:n
797:(
794:O
782:,
770:k
748:n
723:,
711:)
706:n
700:/
694:n
690:4
686:(
683:O
667:,
655:)
650:n
646:2
642:n
639:(
636:O
616:,
604:)
601:!
598:n
595:(
592:O
568:n
513:d
481:G
461:G
451:.
439:G
427:,
415:G
393:G
383:.
371:G
342:G
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
