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