498:, researchers began studying oracles from the point of view of proving lower bounds on algorithms for matroids and related structures. These two papers by Hausmann and Korte both concerned the problem of finding a maximum cardinality independent set, which is easy for matroids but (as they showed) harder to approximate or compute exactly for more general
286:, etc. However, an algorithm for performing computations on arbitrary matroids needs a uniform method of accessing its argument, rather than having to be redesigned for each of these matroid classes. The oracle model provides a convenient way of codifying and classifying the kinds of access that an algorithm might need.
1040:
The basis oracle, the circuit oracle, and the oracle that tests whether a given set is closed are all weaker than the independence oracle: they can be simulated in polynomial time by an algorithm that accesses the matroid using an independence oracle, but not vice versa. Additionally, none of these
65:
that perform computations on matroids have been designed to take an oracle as input, allowing them to run efficiently without change on many different kinds of matroids, and without additional assumptions about what kind of matroid they are using. For instance, given an independence oracle for any
1074:
simultaneous queries, of the prefixes of the sorted order of the matroid elements: an element belongs to the optimal basis if and only if the rank of its prefix differs from the rank of the previous prefix. In contrast, finding a minimum basis with an independence oracle is much slower: it can be
1282:
of a given matroid, a sequence of circuits whose union is the matroid and in which each circuit remains a circuit after all previous circuits in the sequence are contracted. Such a decomposition may also be found with the additional property that a chosen matroid element belongs to every
906:, adding elements of the given set one element at a time, and using the circuit-finding oracle to test whether each addition preserves the independence of the set that has been constructed so far. In the other direction, if an independence oracle is available, the circuit in a set
58:, a subroutine for testing whether a set of matroid elements is independent. Several other types of oracle have also been used; some of them have been shown to be weaker than independence oracles, some stronger, and some equivalent in computational power.
1188:, by algorithms that access the matroid only through an independence oracle or another oracle of equivalent power, without need of any additional assumptions about what kind of matroid has been given to them. These polynomially-solvable problems include:
3297:
minor, respectively. Testing whether a matroid is graphic or regular may be expressed in terms of a finite set of forbidden minors, and may be solved in polynomial time, but the forbidden minors for these problems include the uniform matroid
2062:
502:
represented by an independence oracle. This work kicked off a flurry of papers in the late 1970s and early 1980s showing similar hardness results for problems on matroids and comparing the power of different kinds of matroid oracles.
1036:
is independent and returning the elements for which the answer is no. The independence oracle is also polynomially equivalent to the rank oracle, the spanning oracle, the first two types of closure oracle, and the port oracle.
1903:
1375:
For many matroid problems, it is possible to show that an independence oracle does not provide enough power to allow the problem to be solved in polynomial time. The main idea of these proofs is to find two matroids
2424:
1820:-element subsets of the elements: if it missed one set, it could be fooled by an oracle that chose that same set as the one to make dependent. Therefore, testing for whether a matroid is uniform may require
589:
takes as its input a set of matroid elements, and returns as output a
Boolean value, true if the given set is spanning (i.e. contains a basis and has the same rank as the whole matroid) and false otherwise.
506:
Since that time, the independence oracle has become standard for most research on matroid algorithms. There has also been continued research on lower bounds, and comparisons of different types of oracle.
582:
have been considered: one that tests if a given element belongs to the closure of a given set, a second one that returns the closure of the set, and a third one that tests whether a given set is closed.
2250:
1034:
1203:
Partitioning the elements of a matroid into a minimum number of independent sets, and finding the largest set that is simultaneously independent in two given matroids. The latter problem is called
1174:
2099:
2627:
Computing the girth (size of the smallest circuit), size of the largest circuit, number of circuits, number of bases, number of flats, number of maximum-rank flats, size of the largest flat,
109:
Although some authors have experimented with computer representations of matroids that explicitly list all independent sets or all basis sets of the matroid, these representations are not
2581:
2555:
2529:
1108:
1638:
3332:
3291:
938:
455:
254:
619:
3105:
2203:
1961:
1788:
1665:
1543:
1472:
1423:
1262:
988:
2337:
2279:
2154:
1908:
independence queries, much higher than polynomial. Even a randomized algorithm must make nearly as many queries in order to be confident of distinguishing these two matroids.
1818:
1717:
2449:
2308:
3231:
3077:
3051:
2677:
2655:
2503:
2481:
2176:
2125:
1934:
1761:
1739:
1687:
1594:
1572:
1516:
1494:
1445:
1396:
1364:
1342:
1320:
1230:
1072:
960:
900:
871:
849:
827:
805:
771:
749:
727:
701:
670:
648:
477:
417:
395:
362:
340:
318:
177:
155:
133:
681:
Although there are many known types of oracles, the choice of which to use can be simplified, because many of them are equivalent in computational power. An oracle
1969:
564:
takes as input an independent set and an additional element, and either determines that their union is independent, or finds a circuit in the union and returns it.
527:, true if the given set is independent and false otherwise. It may be implemented easily based on the underlying structure from which the matroid was defined for
1474:
only in the answers to a small number of queries, then it may take a very large number of queries for an algorithm to be sure of distinguishing an input of type
1052:, the rank and independence oracles are significantly different in computational power. The rank oracle allows the construction of a minimum weight basis by
320:-functions" have been studied as one of many equivalent ways of axiomatizing matroids. An independence function maps a set of matroid elements to the number
829:
are polynomially equivalent, then every result that proves the existence or nonexistence of a polynomial time algorithm for a matroid problem using oracle
650:
of the matroid takes as its input a set of matroid elements, and returns as output a
Boolean value, true if the given set contains a circuit that includes
1963:
on the same set of elements but with differing problem answers, an algorithm that correctly solves the given problem on those elements must use at least
375:, in studying matroid partition problems, assumed that the access to the given matroid was through a subroutine that takes as input an independent set
1826:
596:
takes as its input a set of matroid elements, and returns as its output a numerical value, the size of the smallest circuit within that set (or
3167:. In contrast, it is not possible for deterministic algorithms to approximate the number of bases of a matroid accurately in polynomial time (
2342:
85:
proving that certain matroid problems cannot be solved in polynomial time, without invoking unproved assumptions such as the assumption that
1041:
three oracles can simulate each other within polynomial time. The girth oracle is stronger than the independence oracle, in the same sense.
553:
takes as its input a set of matroid elements, and returns as output a
Boolean value, true if the given set is a circuit and false otherwise.
1741:
dependent instead of independent. In order for an algorithm to correctly test whether its input is uniform, it must be able to distinguish
3950:
Mathematical
Foundations of Computer Science 1981, Proceedings, 10th Symposium Štrbské Pleso, Czechoslovakia August 31 – September 4, 1981
546:
takes as its input a set of matroid elements, and returns as output a
Boolean value, true if the given set is a basis and false otherwise.
259:
from which it follows that any explicit representation capable of handling all possible matroids would necessarily use exponential space.
3107:
is much more difficult ... We do not know how this can be efficiently accomplished for binary matroids, let alone for general matroids."
70:
that adds elements to the basis in sorted order by weight, using the independence oracle to test whether each element can be added.
3797:
3511:; Hellerstein, Lisa (1996), "Independence and port oracles for matroids, with an application to computational learning theory",
2208:
262:
Instead, different types of matroids may be represented more efficiently from the other structures from which they are defined:
2657:-element matroids, the fraction of the properties that do not require exponential time to test goes to zero, in the limit, as
2597:
Solving the matroid matching problem, in which the input is a graph and a matroid on its vertices, and the goal is to find a
993:
3846:; Boros, E.; Elbassioni, K.; Gurvich, V.; Makino, K. (2005), "On the complexity of some enumeration problems for matroids",
1113:
4024:
3848:
1297:
2070:
3645:
Fujishige, Satoru; Zhang, Xiaodong (1995), "An efficient cost scaling algorithm for the independent assignment problem",
3616:
2601:
in the graph that is as large as possible, subject to the constraint that the matched vertices form an independent set.
1044:
As well as polynomial time Turing reductions, other types of reducibility have been considered as well. In particular,
2454:
Problems that have been proven to be impossible for a matroid oracle algorithm to compute in polynomial time include:
2557:, then it is not possible to test in polynomial time whether a given matroid contains one or more of the matroids in
1425:
on which the answer to the problem differs and which are difficult for an algorithm to tell apart. In particular, if
487:), and observed that the information it provides is sufficient to find the minimum weight basis in polynomial time.
4395:
4105:
4072:
3892:
2560:
2534:
2508:
1078:
74:
1599:
3668:
3666:
Hausmann, Dirk; Korte, Bernhard (1978), "Lower bounds on the worst-case complexity of some oracle algorithms",
3406:
3301:
3260:
909:
426:
3577:
3487:, Contemporary Mathematics, vol. 197, Providence, RI: American Mathematical Society, pp. 371–376,
189:
4441:
4314:
4280:
4067:
599:
3948:
Korte, B.; Schrader, R. (1981), "A survey on oracle techniques", in Gruska, Jozef; Chytil, Michal (eds.),
3082:
3053:
was announced by
Cunningham and Edmonds at roughly the same time, but appears not to have been published.
1239:
1344:, with the additional assumption that the number of bases is within a polynomial factor of the number of
965:
483:
used a subroutine that tests whether a given set is independent (that is, in more modern terminology, an
180:
3923:
Korte, Bernhard; Hausmann, Dirk (1978), "An analysis of the greedy heuristic for independence systems",
3826:
Kelmans, A. K.; Polesskiĭ, V. P. (1994), "Extremal sets and covering and packing problems in matroids",
2313:
2255:
2130:
1548:
A simple example of this approach can be used to show that it is difficult to test whether a matroid is
777:
as measured in terms of the number of elements of the matroid; in complexity-theoretic terms, this is a
3830:, Amer. Math. Soc. Transl. Ser. 2, vol. 158, Providence, RI: Amer. Math. Soc., pp. 149–174,
1793:
1692:
3755:
3544:
2429:
2288:
2181:
1939:
1766:
1643:
1521:
1450:
1401:
539:, and linear matroids, and for matroids formed from these by standard operations such as direct sums.
4376:
3862:
3542:
Cunningham, William H. (1986), "Improved bounds for matroid partition and intersection algorithms",
3214:
3060:
3034:
2660:
2638:
2486:
2464:
2159:
2108:
1917:
1744:
1722:
1670:
1577:
1555:
1499:
1477:
1428:
1379:
1347:
1325:
1303:
1213:
1055:
943:
883:
854:
832:
810:
788:
754:
732:
710:
684:
653:
631:
460:
400:
378:
345:
323:
301:
160:
138:
116:
3701:
Mathematical programming at
Oberwolfach (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979)
876:
For instance, the independence oracle is polynomially equivalent to the circuit-finding oracle of
4436:
2598:
2826:
For additional research on matroids based on the independence function axiomatization, see e.g.
3857:
880:. If a circuit-finding oracle is available, a set may be tested for independence using at most
571:
takes as its input a set of matroid elements, and returns as its output a numerical value, the
4009:, Colloq. Math. Soc. János Bolyai, vol. 25, Amsterdam: North-Holland, pp. 495–517,
2057:{\displaystyle {\frac {|\operatorname {aut} (M)|}{\sum _{i}|\operatorname {fix} (M,Q_{i})|}}}
1293:
Listing all of the bases, flats, or circuits of a matroid, in polynomial time per output set.
4002:
89:. Problems that have been shown to be hard in this way include testing whether a matroid is
4418:
4367:
4338:
4306:
4272:
4252:
4231:
4199:
4179:
4159:
4126:
4095:
4055:
4014:
3994:
3965:
3940:
3915:
3879:
3835:
3818:
3776:
3745:
3716:
3691:
3658:
3637:
3603:
3565:
3534:
3500:
3471:
3450:
3427:
3379:
1287:
1204:
420:
283:
8:
3462:
Bixby, Robert E.; Cunningham, William H. (1979), "Matroids, graphs, and 3-connectivity",
2609:
2591:
532:
499:
368:
of the family of independent sets, essentially the same thing as an independence oracle.
86:
36:
4256:
4183:
3699:
Hausmann, D.; Korte, B. (1981), "Algorithmic versus axiomatic definitions of matroids",
3454:
371:
Matroid oracles have also been part of the earliest algorithmic work on matroids. Thus,
4033:
3440:
2102:
1049:
365:
271:
4359:
3952:, Lecture Notes in Computer Science, vol. 118, Berlin: Springer, pp. 61–77,
3932:
66:
matroid, it is possible to find the minimum weight basis of the matroid by applying a
4118:
3906:
3810:
3753:
Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms",
3682:
3508:
3419:
2613:
1790:. But in order for a deterministic algorithm to do so, it must test every one of the
1279:
4404:
4355:
4326:
4294:
4260:
4219:
4187:
4147:
4114:
4081:
4043:
3982:
3953:
3928:
3901:
3867:
3843:
3806:
3764:
3733:
3704:
3677:
3625:
3589:
3553:
3522:
3488:
3464:
Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977)
3415:
2628:
2621:
2617:
2281:
to itself. For instance, the automorphism group of the uniform matroid is just the
1197:
1193:
778:
67:
48:
3294:
4414:
4363:
4346:
Truemper, K. (1982), "On the efficiency of representability tests for matroids",
4334:
4302:
4268:
4227:
4195:
4155:
4122:
4091:
4051:
4010:
3990:
3961:
3936:
3911:
3875:
3831:
3814:
3784:
3772:
3741:
3712:
3687:
3654:
3633:
3599:
3561:
3530:
3496:
3467:
3423:
3375:
2688:
2282:
1549:
1272:
1268:
1185:
774:
528:
267:
263:
94:
1898:{\displaystyle {\binom {n}{n/2}}=\Omega \left({\frac {2^{n}}{\sqrt {n}}}\right)}
4330:
4191:
4086:
3492:
3401:
2697:
2587:
1290:
of a given matroid, whenever its branch-width is no more than a fixed constant.
279:
90:
78:
4264:
4223:
3986:
3973:
Lazarson, T. (1958), "The representation problem for independence functions",
3871:
3737:
4430:
4285:
4240:
4135:
3957:
3792:
3513:
3480:
3397:
751:
may be simulated by an algorithm that accesses the matroid using only oracle
524:
98:
44:
3404:(1994), "On the problem of approximating the number of bases of a matroid",
4409:
4207:
4167:
3887:
3611:
3573:
2692:
2605:
1914:
formalize this approach by proving that, whenever there exist two matroids
572:
40:
4151:
4022:
Mayhew, Dillon (2008), "Matroid complexity and nonsuccinct descriptions",
3925:
Algorithmic
Aspects of Combinatorics (Conf., Vancouver Island, B.C., 1976)
3594:
135:
elements may expand into a representation that takes space exponential in
4390:
4063:
82:
2310:, and in the problem of testing uniform matroids there was only one set
4298:
3708:
3629:
3526:
2419:{\displaystyle \scriptstyle |\operatorname {fix} (M,Q_{i})|=(n/2)!^{2}}
1207:, and the solutions to both problems are closely related to each other.
35:, an abstract combinatorial structure that can be used to describe the
24:
4047:
2531:
is a fixed finite set of matroids, and there is no uniform matroid in
523:
takes as its input a set of matroid elements, and returns as output a
4038:
3788:
3724:
Ingleton, A. W. (1959), "A note on independence functions and rank",
3358:
for the existence of a field over which the matroid is representable.
903:
62:
28:
3768:
3557:
3237:
applies the same idea to a non-uniform but highly symmetric matroid.
3703:, Mathematical Programming Studies, vol. 14, pp. 98–111,
3445:
4103:
Piff, M. J. (1973), "An upper bound for the number of matroids",
2594:, or whether there exists a field over which it is representable.
536:
275:
32:
4245:
Mathematical
Proceedings of the Cambridge Philosophical Society
3927:, Annals of Discrete Mathematics, vol. 2, pp. 65–74,
3842:
3152:
2918:
2505:
is uniform with rank or corank at most one. More generally, if
4243:(1980), "The computational complexity of matroid properties",
515:
The following types of matroid oracles have been considered.
4007:
Algebraic methods in graph theory, Vol. I, II (Szeged, 1978)
3828:
Selected topics in discrete mathematics (Moscow, 1972–1990)
3483:(1996), "Randomised approximation of the number of bases",
3434:
3031:. A paper claiming a similar result for any fixed constant
2799:
2156:
denotes the family of sets whose independence differs from
479:, if it exists) or determines that no such circuit exists.
2245:{\displaystyle \scriptstyle \operatorname {fix} (M,Q_{i})}
3578:"Minimum partition of a matroid into independent subsets"
3257:
give special cases of this for the problems of finding a
2461:
Testing whether a given matroid contains a fixed matroid
3582:
Journal of
Research of the National Bureau of Standards
1496:
from an input formed by using one of the symmetries of
1029:{\displaystyle \scriptstyle I\setminus \{y\}\cup \{x\}}
3334:, so they do not contradict this impossibility result.
3305:
3264:
3218:
3086:
3064:
3038:
2664:
2642:
2564:
2538:
2512:
2490:
2468:
2433:
2346:
2317:
2292:
2259:
2212:
2185:
2163:
2134:
2112:
2074:
1943:
1921:
1797:
1770:
1748:
1726:
1696:
1674:
1647:
1603:
1581:
1559:
1525:
1503:
1481:
1454:
1432:
1405:
1383:
1351:
1329:
1307:
1243:
1217:
1184:
Many problems on matroids are known to be solvable in
1169:{\displaystyle \scriptstyle \Omega ((n/\log n)^{1/3})}
1117:
1082:
1059:
997:
969:
947:
913:
887:
858:
836:
814:
792:
758:
736:
714:
688:
676:
657:
635:
603:
464:
430:
404:
382:
349:
327:
305:
164:
142:
120:
3304:
3263:
3217:
3085:
3063:
3037:
2663:
2641:
2563:
2537:
2511:
2489:
2467:
2432:
2345:
2316:
2291:
2258:
2211:
2184:
2162:
2133:
2111:
2073:
1972:
1942:
1920:
1829:
1796:
1769:
1747:
1725:
1695:
1673:
1646:
1602:
1580:
1558:
1524:
1502:
1480:
1453:
1431:
1404:
1382:
1350:
1328:
1306:
1298:
fully polynomial-time randomized approximation scheme
1242:
1216:
1116:
1081:
1058:
996:
968:
946:
912:
886:
857:
835:
813:
791:
785:
if they are polynomially reducible to each other. If
757:
735:
713:
687:
656:
634:
602:
463:
429:
403:
381:
348:
326:
304:
192:
163:
141:
119:
4317:; Walton, P. N. (1981), "Detecting matroid minors",
3435:
Bansal, N.; Pendavingh, R.; van der Pol, J. (2012),
2094:{\displaystyle \scriptstyle \operatorname {aut} (M)}
3647:
Journal of the Operations Research Society of Japan
3507:
3207:. In most of the applications of this technique in
3000:
2950:
2727:
4138:(1971), "The number of combinatorial geometries",
3783:
3478:
3326:
3285:
3225:
3164:
3099:
3071:
3045:
2946:
2914:
2671:
2649:
2575:
2549:
2523:
2497:
2475:
2443:
2418:
2331:
2302:
2273:
2244:
2197:
2170:
2148:
2119:
2093:
2056:
1955:
1928:
1897:
1812:
1782:
1755:
1733:
1711:
1681:
1659:
1632:
1588:
1566:
1537:
1510:
1488:
1466:
1439:
1417:
1390:
1358:
1336:
1314:
1256:
1224:
1168:
1102:
1066:
1045:
1028:
982:
954:
932:
894:
865:
843:
821:
799:
765:
743:
721:
695:
664:
642:
613:
471:
449:
411:
389:
356:
334:
312:
248:
171:
149:
127:
1856:
1833:
962:calls to the oracle by testing, for each element
54:The most commonly used oracle of this type is an
4428:
3825:
3395:
3374:. However, the special case of this problem for
3168:
2934:
2907:
2252:denotes the subgroup of automorphisms that maps
1447:has a high degree of symmetry, and differs from
4170:(1942), "A theorem on independence relations",
4140:The Bulletin of the London Mathematical Society
3890:(1974), "The asymptotic number of geometries",
3461:
3028:
2715:
2713:
1192:Finding a minimum or maximum weight basis of a
97:, or testing whether it contains certain fixed
4212:Proceedings of the London Mathematical Society
3644:
2910:
4313:
4238:
3947:
3922:
3795:(1988), "The complexity of parallel search",
3698:
3665:
3614:(1971), "Matroids and the greedy algorithm",
3466:, New York: Academic Press, pp. 91–103,
3347:
3246:
3204:
3183:
2985:
2970:
2966:
2890:
2886:
2855:
2814:
2723:
2719:
2590:, is representable over any particular fixed
2483:as a minor, except in the special cases that
495:
491:
157:. Indeed, the number of distinct matroids on
2710:
1022:
1016:
1010:
1004:
926:
920:
443:
437:
3752:
3371:
3355:
3254:
3208:
3200:
3187:
2859:
2800:Bansal, Pendavingh & van der Pol (2012)
2763:
2700:, an oracle-like model for graph algorithms
2576:{\displaystyle \scriptstyle {\mathcal {H}}}
2550:{\displaystyle \scriptstyle {\mathcal {H}}}
2524:{\displaystyle \scriptstyle {\mathcal {H}}}
2458:Testing whether a given matroid is uniform.
1911:
1103:{\displaystyle \scriptstyle O({\sqrt {n}})}
4319:Journal of the London Mathematical Society
4210:(1957), "Note on independence functions",
4062:
3975:Journal of the London Mathematical Society
3726:Journal of the London Mathematical Society
3541:
3140:
3016:
2922:
2903:
1633:{\displaystyle \scriptstyle U{}_{n}^{n/2}}
1110:time steps, and there is a lower bound of
4408:
4133:
4085:
4037:
3905:
3861:
3681:
3593:
3444:
2787:
1176:even for randomized parallel algorithms.
4374:
4345:
4283:(1981), "Recognizing graphic matroids",
4005:(1981), "The matroid matching problem",
3972:
3723:
3351:
3327:{\displaystyle \scriptstyle U{}_{4}^{2}}
3286:{\displaystyle \scriptstyle U{}_{4}^{2}}
3128:
3054:
2863:
2835:
2831:
2426:, smaller by an exponential factor than
933:{\displaystyle \scriptstyle I\cup \{x\}}
902:calls to the oracle by starting from an
450:{\displaystyle \scriptstyle I\cup \{x\}}
4279:
3798:Journal of Computer and System Sciences
3610:
3572:
3343:
3250:
3234:
3179:
3177:
3116:
3012:
2996:
2994:
2981:
2979:
2962:
2851:
2742:
1370:
1296:Approximating the number of bases by a
877:
561:
480:
372:
364:if it is dependent; that is, it is the
19:In mathematics and computer science, a
4429:
4021:
4001:
3378:can be solved in polynomial time as a
3367:
2882:
2880:
2878:
2876:
2874:
2872:
2847:
2810:
2808:
2775:
2759:
2757:
2755:
2753:
2751:
851:also proves the same thing for oracle
249:{\displaystyle 2^{2^{n}n^{-3/2+o(1)}}}
4389:
3886:
2795:
2738:
2736:
2631:, or connectivity of a given matroid.
1233:
614:{\displaystyle \scriptstyle +\infty }
4393:(1966), "Connectivity in matroids",
4206:
4172:The Quarterly Journal of Mathematics
4166:
4102:
4025:SIAM Journal on Discrete Mathematics
3849:SIAM Journal on Discrete Mathematics
3203:, this formalization is surveyed in
3174:
3100:{\displaystyle \scriptstyle k\geq 4}
2991:
2976:
2827:
2791:
1552:. For simplicity of exposition, let
1257:{\displaystyle \scriptstyle k\leq 3}
295:
2869:
2805:
2748:
2635:Among the set of all properties of
2604:Testing whether a given matroid is
2586:Testing whether a given matroid is
1763:from every possible permutation of
1267:Testing whether a given matroid is
983:{\displaystyle \scriptstyle y\in I}
677:Relative power of different oracles
510:
457:(necessarily unique and containing
266:from their two numeric parameters,
16:Subroutine for testing independence
13:
3485:Matroid Theory (Seattle, WA, 1995)
2947:Karp, Upfal & Wigderson (1988)
2733:
2567:
2541:
2515:
2332:{\displaystyle \scriptstyle Q_{i}}
2274:{\displaystyle \scriptstyle Q_{i}}
2149:{\displaystyle \scriptstyle Q_{i}}
1865:
1837:
1118:
1046:Karp, Upfal & Wigderson (1988)
607:
14:
4453:
4348:European Journal of Combinatorics
3346:showed this for binary matroids,
3001:Coullard & Hellerstein (1996)
2951:Coullard & Hellerstein (1996)
2728:Coullard & Hellerstein (1996)
1001:
621:if the given set is independent).
4070:(2007), "Testing branch-width",
3165:Chávez Lomelí & Welsh (1996)
3057:, pp. 186–187, writes "Locating
2935:Azar, Broder & Frieze (1994)
2915:Chávez Lomelí & Welsh (1996)
1813:{\displaystyle \scriptstyle n/2}
1712:{\displaystyle \scriptstyle n/2}
4396:Canadian Journal of Mathematics
4106:Journal of Combinatorial Theory
4073:Journal of Combinatorial Theory
3893:Journal of Combinatorial Theory
3361:
3337:
3240:
3193:
3158:
3146:
3134:
3122:
3110:
3022:
3006:
2956:
2940:
2928:
2896:
2444:{\displaystyle \scriptstyle n!}
2303:{\displaystyle \scriptstyle n!}
2198:{\displaystyle \scriptstyle M'}
1956:{\displaystyle \scriptstyle M'}
1783:{\displaystyle \scriptstyle M'}
1660:{\displaystyle \scriptstyle M'}
1538:{\displaystyle \scriptstyle M'}
1467:{\displaystyle \scriptstyle M'}
1418:{\displaystyle \scriptstyle M'}
298:, "independence functions" or "
104:
75:computational complexity theory
3407:Information Processing Letters
3226:{\displaystyle \scriptstyle M}
3169:Azar, Broder & Frieze 1994
3072:{\displaystyle \scriptstyle k}
3046:{\displaystyle \scriptstyle k}
2908:Kelmans & Polesskiĭ (1994)
2841:
2820:
2781:
2769:
2672:{\displaystyle \scriptstyle n}
2650:{\displaystyle \scriptstyle n}
2498:{\displaystyle \scriptstyle H}
2476:{\displaystyle \scriptstyle H}
2402:
2388:
2381:
2377:
2358:
2348:
2238:
2219:
2171:{\displaystyle \scriptstyle M}
2120:{\displaystyle \scriptstyle M}
2087:
2081:
2047:
2043:
2024:
2014:
1997:
1993:
1987:
1977:
1929:{\displaystyle \scriptstyle M}
1756:{\displaystyle \scriptstyle M}
1734:{\displaystyle \scriptstyle M}
1689:by making a single one of the
1682:{\displaystyle \scriptstyle M}
1589:{\displaystyle \scriptstyle M}
1567:{\displaystyle \scriptstyle n}
1511:{\displaystyle \scriptstyle M}
1489:{\displaystyle \scriptstyle M}
1440:{\displaystyle \scriptstyle M}
1391:{\displaystyle \scriptstyle M}
1359:{\displaystyle \scriptstyle r}
1337:{\displaystyle \scriptstyle r}
1315:{\displaystyle \scriptstyle n}
1225:{\displaystyle \scriptstyle k}
1162:
1145:
1124:
1121:
1096:
1086:
1067:{\displaystyle \scriptstyle n}
955:{\displaystyle \scriptstyle n}
895:{\displaystyle \scriptstyle n}
866:{\displaystyle \scriptstyle Y}
844:{\displaystyle \scriptstyle X}
822:{\displaystyle \scriptstyle Y}
800:{\displaystyle \scriptstyle X}
766:{\displaystyle \scriptstyle Y}
744:{\displaystyle \scriptstyle X}
722:{\displaystyle \scriptstyle Y}
696:{\displaystyle \scriptstyle X}
665:{\displaystyle \scriptstyle x}
643:{\displaystyle \scriptstyle x}
472:{\displaystyle \scriptstyle x}
412:{\displaystyle \scriptstyle x}
390:{\displaystyle \scriptstyle I}
357:{\displaystyle \scriptstyle 0}
335:{\displaystyle \scriptstyle 1}
313:{\displaystyle \scriptstyle I}
239:
233:
172:{\displaystyle \scriptstyle n}
150:{\displaystyle \scriptstyle n}
128:{\displaystyle \scriptstyle n}
1:
4360:10.1016/s0195-6698(82)80039-5
3933:10.1016/S0167-5060(08)70322-4
3388:
3029:Bixby & Cunningham (1979)
1210:Testing whether a matroid is
1179:
781:. Two oracles are said to be
342:if the set is independent or
4119:10.1016/0095-8956(73)90006-3
3907:10.1016/0097-3165(74)90063-6
3811:10.1016/0022-0000(88)90027-X
3683:10.1016/0012-365X(78)90097-3
3420:10.1016/0020-0190(94)90037-X
2911:Fujishige & Zhang (1995)
1232:-connected (in the sense of
1075:solved deterministically in
490:Beginning from the work of
51:, among other applications.
7:
3348:Seymour & Walton (1981)
3247:Seymour & Walton (1981)
3205:Korte & Schrader (1981)
3184:Robinson & Welsh (1980)
2986:Hausmann & Korte (1981)
2971:Hausmann & Korte (1981)
2967:Robinson & Welsh (1980)
2891:Hausmann & Korte (1981)
2887:Robinson & Welsh (1980)
2856:Seymour & Walton (1981)
2815:Robinson & Welsh (1980)
2724:Hausmann & Korte (1981)
2720:Robinson & Welsh (1980)
2691:, an oracle-like model for
2682:
940:may be found using at most
496:Hausmann & Korte (1978)
492:Korte & Hausmann (1978)
10:
4458:
4087:10.1016/j.jctb.2006.06.006
3354:for arbitrary fields, and
289:
4265:10.1017/S0305004100056498
3872:10.1137/S0895480103428338
3756:SIAM Journal on Computing
3545:SIAM Journal on Computing
3437:On the number of matroids
3372:Jensen & Korte (1982)
3356:Jensen & Korte (1982)
3255:Jensen & Korte (1982)
3209:Jensen & Korte (1982)
3201:Jensen & Korte (1982)
3188:Jensen & Korte (1982)
2860:Jensen & Korte (1982)
2764:Jensen & Korte (1982)
1912:Jensen & Korte (1982)
1667:be a matroid formed from
81:has led to unconditional
4331:10.1112/jlms/s2-23.2.193
4192:10.1093/qmath/os-13.1.83
3958:10.1007/3-540-10856-4_74
3617:Mathematical Programming
3141:Oum & Seymour (2007)
2923:Oum & Seymour (2007)
2704:
4224:10.1112/plms/s3-7.1.300
3987:10.1112/jlms/s1-33.1.21
3738:10.1112/jlms/s1-34.1.49
3153:Khachiyan et al. (2005)
2919:Khachiyan et al. (2005)
2788:Piff & Welsh (1971)
1719:-element basis sets of
1596:be the uniform matroid
783:polynomially equivalent
419:, and either returns a
4410:10.4153/CJM-1966-129-2
3493:10.1090/conm/197/02534
3479:Chávez Lomelí, Laura;
3328:
3287:
3227:
3101:
3073:
3047:
2673:
2651:
2577:
2551:
2525:
2499:
2477:
2445:
2420:
2333:
2304:
2275:
2246:
2199:
2172:
2150:
2121:
2095:
2058:
1957:
1930:
1899:
1814:
1784:
1757:
1735:
1713:
1683:
1661:
1634:
1590:
1568:
1539:
1512:
1490:
1468:
1441:
1419:
1392:
1360:
1338:
1316:
1258:
1226:
1170:
1104:
1068:
1030:
984:
956:
934:
896:
867:
845:
823:
801:
767:
745:
723:
705:polynomially reducible
697:
666:
644:
615:
558:circuit-finding oracle
473:
451:
413:
391:
358:
336:
314:
250:
173:
151:
129:
4378:Matroid Decomposition
4375:Truemper, K. (1998),
3595:10.6028/jres.069b.004
3509:Coullard, Collette R.
3329:
3288:
3228:
3102:
3074:
3048:
2674:
2652:
2578:
2552:
2526:
2500:
2478:
2446:
2421:
2334:
2305:
2276:
2247:
2200:
2173:
2151:
2122:
2096:
2059:
1958:
1931:
1900:
1815:
1785:
1758:
1736:
1714:
1684:
1662:
1635:
1591:
1569:
1540:
1513:
1491:
1469:
1442:
1420:
1393:
1361:
1339:
1317:
1300:, for a matroid with
1259:
1227:
1171:
1105:
1069:
1031:
985:
957:
935:
897:
868:
846:
824:
802:
768:
746:
724:
698:
667:
645:
616:
474:
452:
414:
392:
359:
337:
315:
251:
174:
152:
130:
39:between vectors in a
3669:Discrete Mathematics
3380:matroid intersection
3302:
3261:
3215:
3199:As well as being in
3083:
3061:
3035:
2661:
2639:
2561:
2535:
2509:
2487:
2465:
2430:
2343:
2314:
2289:
2256:
2209:
2182:
2160:
2131:
2109:
2071:
1970:
1940:
1918:
1827:
1794:
1767:
1745:
1723:
1693:
1671:
1644:
1600:
1578:
1556:
1522:
1500:
1478:
1451:
1429:
1402:
1380:
1371:Impossibility proofs
1348:
1326:
1304:
1288:branch-decomposition
1240:
1214:
1205:matroid intersection
1114:
1079:
1056:
994:
966:
944:
910:
884:
855:
833:
811:
789:
755:
733:
711:
685:
672:and false otherwise.
654:
632:
628:for a fixed element
600:
533:transversal matroids
500:independence systems
461:
427:
401:
379:
346:
324:
302:
190:
181:doubly exponentially
161:
139:
117:
4442:Computation oracles
4257:1980MPCPS..87...29R
4184:1942QJMat..13...83R
4152:10.1112/blms/3.1.55
3455:2012arXiv1206.6270B
3350:for finite fields,
3322:
3281:
1628:
1050:parallel algorithms
521:independence oracle
485:independence oracle
272:bicircular matroids
56:independence oracle
37:linear dependencies
4384:(revised ed.)
4299:10.1007/BF02579179
3709:10.1007/BFb0120924
3630:10.1007/BF01584082
3527:10.1007/BF01844845
3324:
3323:
3309:
3283:
3282:
3268:
3223:
3222:
3097:
3096:
3079:-sums for general
3069:
3068:
3043:
3042:
2679:goes to infinity.
2669:
2668:
2647:
2646:
2573:
2572:
2547:
2546:
2521:
2520:
2495:
2494:
2473:
2472:
2441:
2440:
2416:
2415:
2329:
2328:
2300:
2299:
2271:
2270:
2242:
2241:
2195:
2194:
2168:
2167:
2146:
2145:
2117:
2116:
2103:automorphism group
2091:
2090:
2054:
2012:
1953:
1952:
1926:
1925:
1895:
1810:
1809:
1780:
1779:
1753:
1752:
1731:
1730:
1709:
1708:
1679:
1678:
1657:
1656:
1630:
1629:
1607:
1586:
1585:
1564:
1563:
1535:
1534:
1508:
1507:
1486:
1485:
1464:
1463:
1437:
1436:
1415:
1414:
1388:
1387:
1356:
1355:
1334:
1333:
1322:elements and rank
1312:
1311:
1254:
1253:
1222:
1221:
1166:
1165:
1100:
1099:
1064:
1063:
1026:
1025:
980:
979:
952:
951:
930:
929:
892:
891:
863:
862:
841:
840:
819:
818:
797:
796:
763:
762:
741:
740:
719:
718:
707:to another oracle
693:
692:
662:
661:
640:
639:
611:
610:
469:
468:
447:
446:
409:
408:
387:
386:
366:indicator function
354:
353:
332:
331:
310:
309:
246:
169:
168:
147:
146:
125:
124:
4321:, Second Series,
4239:Robinson, G. C.;
4174:, Second Series,
4048:10.1137/050640576
3977:, Second Series,
3728:, Second Series,
3017:Cunningham (1986)
2904:Cunningham (1986)
2052:
2003:
1889:
1888:
1854:
1280:ear decomposition
1094:
575:of the given set.
113:: a matroid with
27:through which an
4449:
4421:
4412:
4385:
4383:
4370:
4341:
4309:
4275:
4234:
4214:, Third Series,
4202:
4162:
4129:
4098:
4089:
4058:
4041:
4017:
3997:
3968:
3943:
3918:
3909:
3888:Knuth, Donald E.
3882:
3865:
3838:
3821:
3785:Karp, Richard M.
3779:
3748:
3719:
3694:
3685:
3661:
3640:
3606:
3597:
3568:
3537:
3503:
3474:
3457:
3448:
3430:
3383:
3376:bipartite graphs
3365:
3359:
3341:
3335:
3333:
3331:
3330:
3325:
3321:
3316:
3311:
3292:
3290:
3289:
3284:
3280:
3275:
3270:
3244:
3238:
3233:is uniform, but
3232:
3230:
3229:
3224:
3197:
3191:
3181:
3172:
3162:
3156:
3150:
3144:
3138:
3132:
3126:
3120:
3114:
3108:
3106:
3104:
3103:
3098:
3078:
3076:
3075:
3070:
3052:
3050:
3049:
3044:
3026:
3020:
3010:
3004:
2998:
2989:
2983:
2974:
2960:
2954:
2944:
2938:
2932:
2926:
2900:
2894:
2884:
2867:
2845:
2839:
2824:
2818:
2812:
2803:
2785:
2779:
2773:
2767:
2761:
2746:
2740:
2731:
2717:
2678:
2676:
2675:
2670:
2656:
2654:
2653:
2648:
2629:Tutte polynomial
2582:
2580:
2579:
2574:
2571:
2570:
2556:
2554:
2553:
2548:
2545:
2544:
2530:
2528:
2527:
2522:
2519:
2518:
2504:
2502:
2501:
2496:
2482:
2480:
2479:
2474:
2450:
2448:
2447:
2442:
2425:
2423:
2422:
2417:
2414:
2413:
2398:
2384:
2376:
2375:
2351:
2338:
2336:
2335:
2330:
2327:
2326:
2309:
2307:
2306:
2301:
2280:
2278:
2277:
2272:
2269:
2268:
2251:
2249:
2248:
2243:
2237:
2236:
2204:
2202:
2201:
2196:
2193:
2177:
2175:
2174:
2169:
2155:
2153:
2152:
2147:
2144:
2143:
2126:
2124:
2123:
2118:
2100:
2098:
2097:
2092:
2063:
2061:
2060:
2055:
2053:
2051:
2050:
2042:
2041:
2017:
2011:
2001:
2000:
1980:
1974:
1962:
1960:
1959:
1954:
1951:
1935:
1933:
1932:
1927:
1904:
1902:
1901:
1896:
1894:
1890:
1884:
1883:
1882:
1873:
1861:
1860:
1859:
1853:
1849:
1836:
1819:
1817:
1816:
1811:
1805:
1789:
1787:
1786:
1781:
1778:
1762:
1760:
1759:
1754:
1740:
1738:
1737:
1732:
1718:
1716:
1715:
1710:
1704:
1688:
1686:
1685:
1680:
1666:
1664:
1663:
1658:
1655:
1639:
1637:
1636:
1631:
1627:
1623:
1614:
1609:
1595:
1593:
1592:
1587:
1573:
1571:
1570:
1565:
1544:
1542:
1541:
1536:
1533:
1517:
1515:
1514:
1509:
1495:
1493:
1492:
1487:
1473:
1471:
1470:
1465:
1462:
1446:
1444:
1443:
1438:
1424:
1422:
1421:
1416:
1413:
1397:
1395:
1394:
1389:
1365:
1363:
1362:
1357:
1343:
1341:
1340:
1335:
1321:
1319:
1318:
1313:
1263:
1261:
1260:
1255:
1231:
1229:
1228:
1223:
1198:greedy algorithm
1194:weighted matroid
1175:
1173:
1172:
1167:
1161:
1160:
1156:
1134:
1109:
1107:
1106:
1101:
1095:
1090:
1073:
1071:
1070:
1065:
1048:showed that, in
1035:
1033:
1032:
1027:
989:
987:
986:
981:
961:
959:
958:
953:
939:
937:
936:
931:
901:
899:
898:
893:
872:
870:
869:
864:
850:
848:
847:
842:
828:
826:
825:
820:
806:
804:
803:
798:
779:Turing reduction
772:
770:
769:
764:
750:
748:
747:
742:
728:
726:
725:
720:
702:
700:
699:
694:
671:
669:
668:
663:
649:
647:
646:
641:
620:
618:
617:
612:
529:graphic matroids
511:Types of oracles
478:
476:
475:
470:
456:
454:
453:
448:
418:
416:
415:
410:
396:
394:
393:
388:
363:
361:
360:
355:
341:
339:
338:
333:
319:
317:
316:
311:
268:graphic matroids
264:uniform matroids
255:
253:
252:
247:
245:
244:
243:
242:
223:
207:
206:
178:
176:
175:
170:
156:
154:
153:
148:
134:
132:
131:
126:
68:greedy algorithm
4457:
4456:
4452:
4451:
4450:
4448:
4447:
4446:
4427:
4426:
4425:
4381:
4241:Welsh, D. J. A.
4136:Welsh, D. J. A.
3863:10.1.1.124.4286
3769:10.1137/0211014
3558:10.1137/0215066
3391:
3386:
3366:
3362:
3352:Truemper (1982)
3342:
3338:
3317:
3312:
3310:
3303:
3300:
3299:
3276:
3271:
3269:
3262:
3259:
3258:
3245:
3241:
3216:
3213:
3212:
3198:
3194:
3182:
3175:
3163:
3159:
3151:
3147:
3139:
3135:
3129:Truemper (1982)
3127:
3123:
3115:
3111:
3084:
3081:
3080:
3062:
3059:
3058:
3055:Truemper (1998)
3036:
3033:
3032:
3027:
3023:
3011:
3007:
2999:
2992:
2984:
2977:
2961:
2957:
2945:
2941:
2933:
2929:
2901:
2897:
2885:
2870:
2864:Truemper (1982)
2846:
2842:
2836:Ingleton (1959)
2832:Lazarson (1958)
2825:
2821:
2813:
2806:
2786:
2782:
2774:
2770:
2762:
2749:
2741:
2734:
2718:
2711:
2707:
2689:Black box group
2685:
2662:
2659:
2658:
2640:
2637:
2636:
2566:
2565:
2562:
2559:
2558:
2540:
2539:
2536:
2533:
2532:
2514:
2513:
2510:
2507:
2506:
2488:
2485:
2484:
2466:
2463:
2462:
2431:
2428:
2427:
2409:
2405:
2394:
2380:
2371:
2367:
2347:
2344:
2341:
2340:
2322:
2318:
2315:
2312:
2311:
2290:
2287:
2286:
2283:symmetric group
2264:
2260:
2257:
2254:
2253:
2232:
2228:
2210:
2207:
2206:
2186:
2183:
2180:
2179:
2161:
2158:
2157:
2139:
2135:
2132:
2129:
2128:
2110:
2107:
2106:
2072:
2069:
2068:
2067:queries, where
2046:
2037:
2033:
2013:
2007:
2002:
1996:
1976:
1975:
1973:
1971:
1968:
1967:
1944:
1941:
1938:
1937:
1919:
1916:
1915:
1878:
1874:
1872:
1868:
1855:
1845:
1841:
1832:
1831:
1830:
1828:
1825:
1824:
1801:
1795:
1792:
1791:
1771:
1768:
1765:
1764:
1746:
1743:
1742:
1724:
1721:
1720:
1700:
1694:
1691:
1690:
1672:
1669:
1668:
1648:
1645:
1642:
1641:
1619:
1615:
1610:
1608:
1601:
1598:
1597:
1579:
1576:
1575:
1557:
1554:
1553:
1526:
1523:
1520:
1519:
1501:
1498:
1497:
1479:
1476:
1475:
1455:
1452:
1449:
1448:
1430:
1427:
1426:
1406:
1403:
1400:
1399:
1381:
1378:
1377:
1373:
1349:
1346:
1345:
1327:
1324:
1323:
1305:
1302:
1301:
1241:
1238:
1237:
1215:
1212:
1211:
1186:polynomial time
1182:
1152:
1148:
1144:
1130:
1115:
1112:
1111:
1089:
1080:
1077:
1076:
1057:
1054:
1053:
995:
992:
991:
967:
964:
963:
945:
942:
941:
911:
908:
907:
885:
882:
881:
856:
853:
852:
834:
831:
830:
812:
809:
808:
790:
787:
786:
775:polynomial time
756:
753:
752:
734:
731:
730:
729:if any call to
712:
709:
708:
686:
683:
682:
679:
655:
652:
651:
633:
630:
629:
601:
598:
597:
587:spanning oracle
578:Three types of
513:
462:
459:
458:
428:
425:
424:
402:
399:
398:
397:and an element
380:
377:
376:
347:
344:
343:
325:
322:
321:
303:
300:
299:
292:
280:linear matroids
219:
212:
208:
202:
198:
197:
193:
191:
188:
187:
179:elements grows
162:
159:
158:
140:
137:
136:
118:
115:
114:
107:
17:
12:
11:
5:
4455:
4445:
4444:
4439:
4437:Matroid theory
4424:
4423:
4387:
4372:
4354:(3): 275–291,
4343:
4325:(2): 193–203,
4315:Seymour, P. D.
4311:
4281:Seymour, P. D.
4277:
4236:
4204:
4164:
4131:
4100:
4080:(3): 385–393,
4060:
4032:(2): 455–466,
4019:
3999:
3970:
3945:
3920:
3884:
3856:(4): 966–984,
3840:
3823:
3805:(2): 225–253,
3793:Wigderson, Avi
3781:
3763:(1): 184–190,
3750:
3721:
3696:
3676:(3): 261–276,
3663:
3653:(1): 124–136,
3642:
3608:
3570:
3552:(4): 948–957,
3539:
3521:(2): 189–208,
3505:
3481:Welsh, Dominic
3476:
3459:
3432:
3392:
3390:
3387:
3385:
3384:
3360:
3344:Seymour (1981)
3336:
3320:
3315:
3308:
3279:
3274:
3267:
3251:Seymour (1981)
3239:
3235:Seymour (1981)
3221:
3192:
3173:
3157:
3145:
3133:
3121:
3117:Seymour (1981)
3109:
3095:
3092:
3089:
3067:
3041:
3021:
3013:Edmonds (1965)
3005:
2990:
2975:
2963:Edmonds (1971)
2955:
2939:
2927:
2895:
2868:
2852:Seymour (1981)
2840:
2819:
2804:
2780:
2768:
2747:
2743:Edmonds (1971)
2732:
2708:
2706:
2703:
2702:
2701:
2698:Implicit graph
2695:
2684:
2681:
2667:
2645:
2633:
2632:
2625:
2602:
2595:
2584:
2569:
2543:
2517:
2493:
2471:
2459:
2439:
2436:
2412:
2408:
2404:
2401:
2397:
2393:
2390:
2387:
2383:
2379:
2374:
2370:
2366:
2363:
2360:
2357:
2354:
2350:
2325:
2321:
2298:
2295:
2267:
2263:
2240:
2235:
2231:
2227:
2224:
2221:
2218:
2215:
2192:
2189:
2166:
2142:
2138:
2115:
2089:
2086:
2083:
2080:
2077:
2065:
2064:
2049:
2045:
2040:
2036:
2032:
2029:
2026:
2023:
2020:
2016:
2010:
2006:
1999:
1995:
1992:
1989:
1986:
1983:
1979:
1950:
1947:
1924:
1906:
1905:
1893:
1887:
1881:
1877:
1871:
1867:
1864:
1858:
1852:
1848:
1844:
1840:
1835:
1808:
1804:
1800:
1777:
1774:
1751:
1729:
1707:
1703:
1699:
1677:
1654:
1651:
1626:
1622:
1618:
1613:
1606:
1584:
1562:
1532:
1529:
1506:
1484:
1461:
1458:
1435:
1412:
1409:
1386:
1372:
1369:
1368:
1367:
1366:-element sets.
1354:
1332:
1310:
1294:
1291:
1284:
1276:
1265:
1252:
1249:
1246:
1220:
1208:
1201:
1181:
1178:
1164:
1159:
1155:
1151:
1147:
1143:
1140:
1137:
1133:
1129:
1126:
1123:
1120:
1098:
1093:
1088:
1085:
1062:
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
978:
975:
972:
950:
928:
925:
922:
919:
916:
890:
878:Edmonds (1965)
861:
839:
817:
795:
761:
739:
717:
703:is said to be
691:
678:
675:
674:
673:
660:
638:
622:
609:
606:
590:
583:
580:closure oracle
576:
565:
562:Edmonds (1965)
554:
551:circuit oracle
547:
540:
512:
509:
481:Edmonds (1971)
467:
445:
442:
439:
436:
433:
407:
385:
373:Edmonds (1965)
352:
330:
308:
294:Starting with
291:
288:
257:
256:
241:
238:
235:
232:
229:
226:
222:
218:
215:
211:
205:
201:
196:
167:
145:
123:
106:
103:
45:spanning trees
21:matroid oracle
15:
9:
6:
4:
3:
2:
4454:
4443:
4440:
4438:
4435:
4434:
4432:
4420:
4416:
4411:
4406:
4403:: 1301–1324,
4402:
4398:
4397:
4392:
4388:
4380:
4379:
4373:
4369:
4365:
4361:
4357:
4353:
4349:
4344:
4340:
4336:
4332:
4328:
4324:
4320:
4316:
4312:
4308:
4304:
4300:
4296:
4292:
4288:
4287:
4286:Combinatorica
4282:
4278:
4274:
4270:
4266:
4262:
4258:
4254:
4250:
4246:
4242:
4237:
4233:
4229:
4225:
4221:
4217:
4213:
4209:
4205:
4201:
4197:
4193:
4189:
4185:
4181:
4177:
4173:
4169:
4165:
4161:
4157:
4153:
4149:
4145:
4141:
4137:
4134:Piff, M. J.;
4132:
4128:
4124:
4120:
4116:
4112:
4108:
4107:
4101:
4097:
4093:
4088:
4083:
4079:
4075:
4074:
4069:
4068:Seymour, Paul
4065:
4061:
4057:
4053:
4049:
4045:
4040:
4035:
4031:
4027:
4026:
4020:
4016:
4012:
4008:
4004:
4000:
3996:
3992:
3988:
3984:
3980:
3976:
3971:
3967:
3963:
3959:
3955:
3951:
3946:
3942:
3938:
3934:
3930:
3926:
3921:
3917:
3913:
3908:
3903:
3899:
3895:
3894:
3889:
3885:
3881:
3877:
3873:
3869:
3864:
3859:
3855:
3851:
3850:
3845:
3844:Khachiyan, L.
3841:
3837:
3833:
3829:
3824:
3820:
3816:
3812:
3808:
3804:
3800:
3799:
3794:
3790:
3786:
3782:
3778:
3774:
3770:
3766:
3762:
3758:
3757:
3751:
3747:
3743:
3739:
3735:
3731:
3727:
3722:
3718:
3714:
3710:
3706:
3702:
3697:
3693:
3689:
3684:
3679:
3675:
3671:
3670:
3664:
3660:
3656:
3652:
3648:
3643:
3639:
3635:
3631:
3627:
3623:
3619:
3618:
3613:
3612:Edmonds, Jack
3609:
3605:
3601:
3596:
3591:
3587:
3583:
3579:
3575:
3574:Edmonds, Jack
3571:
3567:
3563:
3559:
3555:
3551:
3547:
3546:
3540:
3536:
3532:
3528:
3524:
3520:
3516:
3515:
3514:Combinatorica
3510:
3506:
3502:
3498:
3494:
3490:
3486:
3482:
3477:
3473:
3469:
3465:
3460:
3456:
3452:
3447:
3442:
3438:
3433:
3429:
3425:
3421:
3417:
3413:
3409:
3408:
3403:
3402:Frieze, A. M.
3399:
3398:Broder, A. Z.
3394:
3393:
3381:
3377:
3373:
3369:
3368:Lovász (1981)
3364:
3357:
3353:
3349:
3345:
3340:
3318:
3313:
3306:
3296:
3295:Vámos matroid
3277:
3272:
3265:
3256:
3252:
3249:. Results of
3248:
3243:
3236:
3219:
3210:
3206:
3202:
3196:
3189:
3185:
3180:
3178:
3170:
3166:
3161:
3154:
3149:
3142:
3137:
3130:
3125:
3118:
3113:
3093:
3090:
3087:
3065:
3056:
3039:
3030:
3025:
3018:
3014:
3009:
3002:
2997:
2995:
2987:
2982:
2980:
2972:
2968:
2964:
2959:
2952:
2948:
2943:
2936:
2931:
2924:
2920:
2916:
2912:
2909:
2905:
2899:
2892:
2888:
2883:
2881:
2879:
2877:
2875:
2873:
2865:
2861:
2857:
2853:
2849:
2848:Lovász (1981)
2844:
2837:
2833:
2829:
2823:
2816:
2811:
2809:
2801:
2797:
2793:
2789:
2784:
2777:
2776:Mayhew (2008)
2772:
2765:
2760:
2758:
2756:
2754:
2752:
2744:
2739:
2737:
2729:
2725:
2721:
2716:
2714:
2709:
2699:
2696:
2694:
2690:
2687:
2686:
2680:
2665:
2643:
2630:
2626:
2623:
2619:
2615:
2611:
2607:
2603:
2600:
2596:
2593:
2589:
2585:
2491:
2469:
2460:
2457:
2456:
2455:
2452:
2437:
2434:
2410:
2406:
2399:
2395:
2391:
2385:
2372:
2368:
2364:
2361:
2355:
2352:
2323:
2319:
2296:
2293:
2284:
2265:
2261:
2233:
2229:
2225:
2222:
2216:
2213:
2190:
2187:
2164:
2140:
2136:
2113:
2104:
2084:
2078:
2075:
2038:
2034:
2030:
2027:
2021:
2018:
2008:
2004:
1990:
1984:
1981:
1966:
1965:
1964:
1948:
1945:
1922:
1913:
1909:
1891:
1885:
1879:
1875:
1869:
1862:
1850:
1846:
1842:
1838:
1823:
1822:
1821:
1806:
1802:
1798:
1775:
1772:
1749:
1727:
1705:
1701:
1697:
1675:
1652:
1649:
1624:
1620:
1616:
1611:
1604:
1582:
1574:be even, let
1560:
1551:
1546:
1530:
1527:
1504:
1482:
1459:
1456:
1433:
1410:
1407:
1384:
1352:
1330:
1308:
1299:
1295:
1292:
1289:
1285:
1281:
1277:
1274:
1270:
1266:
1250:
1247:
1244:
1235:
1218:
1209:
1206:
1202:
1199:
1195:
1191:
1190:
1189:
1187:
1177:
1157:
1153:
1149:
1141:
1138:
1135:
1131:
1127:
1091:
1083:
1060:
1051:
1047:
1042:
1038:
1019:
1013:
1007:
998:
976:
973:
970:
948:
923:
917:
914:
905:
888:
879:
874:
859:
837:
815:
793:
784:
780:
776:
759:
737:
715:
706:
689:
658:
636:
627:
623:
604:
595:
591:
588:
584:
581:
577:
574:
570:
566:
563:
559:
555:
552:
548:
545:
541:
538:
534:
530:
526:
525:Boolean value
522:
518:
517:
516:
508:
504:
501:
497:
493:
488:
486:
482:
465:
440:
434:
431:
422:
405:
383:
374:
369:
367:
350:
328:
306:
297:
287:
285:
281:
278:from graphs,
277:
273:
269:
265:
260:
236:
230:
227:
224:
220:
216:
213:
209:
203:
199:
194:
186:
185:
184:
182:
165:
143:
121:
112:
102:
100:
96:
92:
88:
84:
80:
76:
71:
69:
64:
59:
57:
52:
50:
46:
42:
38:
34:
31:may access a
30:
26:
22:
4400:
4394:
4391:Tutte, W. T.
4377:
4351:
4347:
4322:
4318:
4293:(1): 75–78,
4290:
4284:
4251:(1): 29–45,
4248:
4244:
4215:
4211:
4175:
4171:
4143:
4139:
4110:
4109:, Series B,
4104:
4077:
4076:, Series B,
4071:
4064:Oum, Sang-il
4039:math/0702567
4029:
4023:
4006:
3978:
3974:
3949:
3924:
3897:
3896:, Series A,
3891:
3853:
3847:
3827:
3802:
3796:
3760:
3754:
3729:
3725:
3700:
3673:
3667:
3650:
3646:
3621:
3615:
3585:
3581:
3549:
3543:
3518:
3512:
3484:
3463:
3436:
3411:
3405:
3363:
3339:
3293:minor and a
3242:
3195:
3160:
3148:
3136:
3124:
3112:
3024:
3008:
2958:
2942:
2930:
2898:
2843:
2822:
2796:Knuth (1974)
2783:
2771:
2693:group theory
2634:
2453:
2285:, with size
2101:denotes the
2066:
1910:
1907:
1547:
1374:
1183:
1043:
1039:
875:
782:
704:
680:
625:
594:girth oracle
593:
586:
579:
568:
557:
550:
544:basis oracle
543:
520:
514:
505:
489:
484:
370:
293:
261:
258:
110:
108:
105:Why oracles?
83:lower bounds
79:oracle model
72:
60:
55:
53:
41:vector space
20:
18:
4218:: 300–320,
4113:: 241–245,
3900:: 398–400,
3624:: 127–136,
3414:(1): 9–11,
2828:Rado (1957)
2792:Piff (1973)
2610:transversal
2583:as a minor.
1518:to permute
1278:Finding an
626:port oracle
569:rank oracle
296:Rado (1942)
4431:Categories
4003:Lovász, L.
3789:Upfal, Eli
3396:Azar, Y.;
3389:References
2622:orientable
1640:, and let
1286:Finding a
1234:Tutte 1966
1196:, using a
1180:Algorithms
990:, whether
773:and takes
63:algorithms
25:subroutine
4178:: 83–89,
4146:: 55–56,
3981:: 21–25,
3858:CiteSeerX
3732:: 49–56,
3588:: 67–72,
3446:1206.6270
3091:≥
2902:E.g. see
2614:bipartite
2606:self-dual
2356:
2217:
2079:
2022:
2005:∑
1985:
1866:Ω
1248:≤
1139:
1119:Ω
1014:∪
1002:∖
974:∈
918:∪
904:empty set
608:∞
435:∪
214:−
29:algorithm
4208:Rado, R.
4168:Rado, R.
3576:(1965),
3382:problem.
2683:See also
2618:Eulerian
2599:matching
2191:′
1949:′
1776:′
1653:′
1531:′
1460:′
1411:′
1283:circuit.
537:gammoids
284:matrices
276:gammoids
111:succinct
4419:0205880
4368:0679212
4339:0609098
4307:0602418
4273:0549295
4253:Bibcode
4232:0088459
4200:0008250
4180:Bibcode
4160:0282867
4127:0316282
4096:2305892
4056:2399359
4015:0642059
3995:0098701
3966:0652740
3941:0500689
3916:0335312
3880:2206374
3836:1269136
3819:0950432
3777:0646772
3746:0101848
3717:0600125
3692:0523316
3659:1337446
3638:0297357
3604:0190025
3566:0861361
3535:1401892
3501:1411698
3472:0538038
3451:Bibcode
3428:1279491
1550:uniform
1273:regular
1269:graphic
421:circuit
290:History
95:uniform
43:or the
33:matroid
4417:
4366:
4337:
4305:
4271:
4230:
4198:
4158:
4125:
4094:
4054:
4013:
3993:
3964:
3939:
3914:
3878:
3860:
3834:
3817:
3775:
3744:
3715:
3690:
3657:
3636:
3602:
3564:
3533:
3499:
3470:
3426:
2921:, and
2834:, and
2588:binary
2205:, and
1236:) for
274:, and
99:minors
91:binary
87:P ≠ NP
77:, the
4382:(PDF)
4034:arXiv
3441:arXiv
2705:Notes
2620:, or
2592:field
2339:with
282:from
61:Many
49:graph
47:of a
23:is a
3253:and
1936:and
1398:and
807:and
573:rank
556:The
494:and
4405:doi
4356:doi
4327:doi
4295:doi
4261:doi
4220:doi
4188:doi
4148:doi
4115:doi
4082:doi
4044:doi
3983:doi
3954:doi
3929:doi
3902:doi
3868:doi
3807:doi
3765:doi
3734:doi
3705:doi
3678:doi
3626:doi
3590:doi
3586:69B
3554:doi
3523:doi
3489:doi
3416:doi
2353:fix
2214:fix
2178:to
2105:of
2076:aut
2019:fix
1982:aut
1271:or
1136:log
560:of
519:An
423:in
183:as
93:or
73:In
4433::
4415:MR
4413:,
4401:18
4399:,
4364:MR
4362:,
4350:,
4335:MR
4333:,
4323:23
4303:MR
4301:,
4289:,
4269:MR
4267:,
4259:,
4249:87
4247:,
4228:MR
4226:,
4196:MR
4194:,
4186:,
4176:13
4156:MR
4154:,
4142:,
4123:MR
4121:,
4111:14
4092:MR
4090:,
4078:97
4066:;
4052:MR
4050:,
4042:,
4030:22
4028:,
4011:MR
3991:MR
3989:,
3979:33
3962:MR
3960:,
3937:MR
3935:,
3912:MR
3910:,
3898:16
3876:MR
3874:,
3866:,
3854:19
3852:,
3832:MR
3815:MR
3813:,
3803:36
3801:,
3791:;
3787:;
3773:MR
3771:,
3761:11
3759:,
3742:MR
3740:,
3730:34
3713:MR
3711:,
3688:MR
3686:,
3674:24
3672:,
3655:MR
3651:38
3649:,
3634:MR
3632:,
3620:,
3600:MR
3598:,
3584:,
3580:,
3562:MR
3560:,
3550:15
3548:,
3531:MR
3529:,
3519:16
3517:,
3497:MR
3495:,
3468:MR
3449:,
3439:,
3424:MR
3422:,
3412:50
3410:,
3400:;
3370:;
3211:,
3186:;
3176:^
3171:).
3015:;
2993:^
2978:^
2969:;
2965:;
2949:;
2917:,
2913:,
2906:,
2889:;
2871:^
2862:;
2858:;
2854:;
2850:;
2830:,
2807:^
2798:;
2794:;
2790:;
2750:^
2735:^
2726:;
2722:;
2712:^
2616:,
2612:,
2608:,
2451:.
2127:,
1545:.
873:.
624:A
592:A
585:A
567:A
549:A
542:A
535:,
531:,
270:,
101:.
4422:.
4407::
4386:.
4371:.
4358::
4352:3
4342:.
4329::
4310:.
4297::
4291:1
4276:.
4263::
4255::
4235:.
4222::
4216:7
4203:.
4190::
4182::
4163:.
4150::
4144:3
4130:.
4117::
4099:.
4084::
4059:.
4046::
4036::
4018:.
3998:.
3985::
3969:.
3956::
3944:.
3931::
3919:.
3904::
3883:.
3870::
3839:.
3822:.
3809::
3780:.
3767::
3749:.
3736::
3720:.
3707::
3695:.
3680::
3662:.
3641:.
3628::
3622:1
3607:.
3592::
3569:.
3556::
3538:.
3525::
3504:.
3491::
3475:.
3458:.
3453::
3443::
3431:.
3418::
3319:2
3314:4
3307:U
3278:2
3273:4
3266:U
3220:M
3190:.
3155:.
3143:.
3131:.
3119:.
3094:4
3088:k
3066:k
3040:k
3019:.
3003:.
2988:.
2973:.
2953:.
2937:.
2925:.
2893:.
2866:.
2838:.
2817:.
2802:.
2778:.
2766:.
2745:.
2730:.
2666:n
2644:n
2624:.
2568:H
2542:H
2516:H
2492:H
2470:H
2438:!
2435:n
2411:2
2407:!
2403:)
2400:2
2396:/
2392:n
2389:(
2386:=
2382:|
2378:)
2373:i
2369:Q
2365:,
2362:M
2359:(
2349:|
2324:i
2320:Q
2297:!
2294:n
2266:i
2262:Q
2239:)
2234:i
2230:Q
2226:,
2223:M
2220:(
2188:M
2165:M
2141:i
2137:Q
2114:M
2088:)
2085:M
2082:(
2048:|
2044:)
2039:i
2035:Q
2031:,
2028:M
2025:(
2015:|
2009:i
1998:|
1994:)
1991:M
1988:(
1978:|
1946:M
1923:M
1892:)
1886:n
1880:n
1876:2
1870:(
1863:=
1857:)
1851:2
1847:/
1843:n
1839:n
1834:(
1807:2
1803:/
1799:n
1773:M
1750:M
1728:M
1706:2
1702:/
1698:n
1676:M
1650:M
1625:2
1621:/
1617:n
1612:n
1605:U
1583:M
1561:n
1528:M
1505:M
1483:M
1457:M
1434:M
1408:M
1385:M
1353:r
1331:r
1309:n
1275:.
1264:.
1251:3
1245:k
1219:k
1200:.
1163:)
1158:3
1154:/
1150:1
1146:)
1142:n
1132:/
1128:n
1125:(
1122:(
1097:)
1092:n
1087:(
1084:O
1061:n
1023:}
1020:x
1017:{
1011:}
1008:y
1005:{
999:I
977:I
971:y
949:n
927:}
924:x
921:{
915:I
889:n
860:Y
838:X
816:Y
794:X
760:Y
738:X
716:Y
690:X
659:x
637:x
605:+
466:x
444:}
441:x
438:{
432:I
406:x
384:I
351:0
329:1
307:I
240:)
237:1
234:(
231:o
228:+
225:2
221:/
217:3
210:n
204:n
200:2
195:2
166:n
144:n
122:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.