{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T22:17:40Z","timestamp":1775341060933,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1986,6,1]],"date-time":"1986-06-01T00:00:00Z","timestamp":517968000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1986,6]]},"DOI":"10.1007\/bf02579169","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T21:15:33Z","timestamp":1174598133000},"page":"123-150","source":"Crossref","is-referenced-by-count":43,"title":["An augmenting path algorithm for linear matroid parity"],"prefix":"10.1007","volume":"6","author":[{"given":"Harold N.","family":"Gabow","sequence":"first","affiliation":[]},{"given":"Matthias","family":"Stallmann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02579169_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-6666-3","volume-title":"Combinatorial Theory","author":"M. Aigner","year":"1979","unstructured":"M. Aigner,Combinatorial Theory, Springer Verlag, Berlin, 1979."},{"key":"BF02579169_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft andJ. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Ma., 1974."},{"key":"BF02579169_CR3","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1137\/0211038","volume":"11","author":"D. Coppersmith","year":"1982","unstructured":"D. Coppersmith andS. Winograd, On the asymptotic complexity of matrix multiplication,SIAM J. Comput.,11 (1982), 472\u2013492.","journal-title":"SIAM J. Comput."},{"key":"BF02579169_CR4","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, Paths, trees and flowers,Canadian J. of Math.,17 (1965), 449\u2013467.","journal-title":"Canadian J. of Math."},{"key":"BF02579169_CR5","doi-asserted-by":"crossref","unstructured":"S. Even andO. Kariv, AnO(n 2.5) algorithm for maximum matching in general graphs,Proc. 16th Annual IEEE Symp. on Foundations of Computer Science, Berkeley, (1975), 100\u2013112.","DOI":"10.1109\/SFCS.1975.5"},{"key":"BF02579169_CR6","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF01580672","volume":"10","author":"H. N. Gabow","year":"1976","unstructured":"H. N. Gabow, Decomposing symmetric exchanges in matroid bases,Mathematical Programming 10 (1976), 271\u2013276.","journal-title":"Mathematical Programming"},{"key":"BF02579169_CR7","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"H. N. Gabow","year":"1976","unstructured":"H. N. Gabow, An efficient implementation of Edmonds\u2019 algorithm for maximum matching on graphs,J. ACM 23 (1976), 221\u2013234.","journal-title":"J. ACM"},{"key":"BF02579169_CR8","unstructured":"H. N. Gabow andM. Stallmann, Scheduling multi-task jobs with deadlines on one processor,working paper."},{"key":"BF02579169_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/BFb0015746","volume-title":"Automata, Languages and Programming","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow andM. Stallmann, Efficient algorithms for graphic matroid intersection and parity,Automata, Languages and Programming;Lecture Notes in Computer Science 194, (W. Brauer, ed.), Springer-Verlag, New York, 1985, 210\u2013220."},{"key":"BF02579169_CR10","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0196-6774(84)90042-7","volume":"5","author":"H. N. Gabow","year":"1984","unstructured":"H. N. Gabow andR. E. Tarjan, Efficient algorithms for a family of matroid intersection problems,J. Algorithms 5 (1984), 80\u2013131.","journal-title":"J. Algorithms"},{"key":"BF02579169_CR11","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow andR. E. Tarjan, A linear-time algorithm for a special case of disjoint set union,J. of Comp. and Sys. Sciences 30 (1985), 209\u2013221.","journal-title":"J. of Comp. and Sys. Sciences"},{"key":"BF02579169_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey andD. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979."},{"key":"BF02579169_CR13","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1137\/0211014","volume":"11","author":"P. Jensen","year":"1982","unstructured":"P. Jensen andB. Korte, Complexity of matroid property algorithmsSIAM Journal on Computing,11 (1982), 184\u2013190.","journal-title":"SIAM Journal on Computing"},{"key":"BF02579169_CR14","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0012-365X(77)90118-2","volume":"19","author":"S. Krogdahl","year":"1977","unstructured":"S. Krogdahl, The dependence graph for bases in matroids,Discrete Mathematics 19 (1977), 47\u201359.","journal-title":"Discrete Mathematics"},{"key":"BF02579169_CR15","unstructured":"E. L. Lawler, Matroids with parity conditions: a new class of combinatorial optimization problems,Electronics Research Laboratory, Berkeley, Memorandum Number ERL\u2014M334 (1971)."},{"key":"BF02579169_CR16","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. L. Lawler","year":"1976","unstructured":"E. L. Lawler,Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, San Francisco, 1976."},{"key":"BF02579169_CR17","volume-title":"Algebraic Methods in Graph Theory","author":"L. Lov\u00e1sz","year":"1978","unstructured":"L. Lov\u00e1sz, The matroid matching problem,Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis J\u00e1nos Bolyai, Szeged (Hungary), 1978."},{"key":"BF02579169_CR18","first-page":"121","volume":"42","author":"L. Lov\u00e1sz","year":"1980","unstructured":"L. Lov\u00e1sz, Selecting independent lines from a family of lines in space,Acta Scientarium Mathematicarum,42 (1980), 121\u2013131.","journal-title":"Acta Scientarium Mathematicarum"},{"key":"BF02579169_CR19","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/0095-8956(80)90066-0","volume":"28","author":"L. Lov\u00e1sz","year":"1980","unstructured":"L. Lov\u00e1sz, Matroid matching and some applications,J. Comb. Theory, B,28 (1980), 208\u2013236.","journal-title":"J. Comb. Theory, B"},{"key":"BF02579169_CR20","doi-asserted-by":"crossref","unstructured":"S. Micali andV. V. Vazirani, AnO(\u221a|V|\u00b7|E|) algorithm for finding maximum matching in general graphs,Proc. 20th Annual IEEE Symp. on Foundations of Computer Science, 1980, 17\u201327.","DOI":"10.1109\/SFCS.1980.12"},{"key":"BF02579169_CR21","unstructured":"J. B. Orlin andJ. H. Vande Vate, An algorithm for the linear matroid parity problem,manuscript."},{"key":"BF02579169_CR22","doi-asserted-by":"crossref","unstructured":"Po Tong, E. L. Lawler andV. V. Vazirani, Solving the weighted parity problem for gammoids by reduction to graphic matching,In: Combinatorial Optimization, (W. R. Pulleyblank, ed.), Academic Press, 1984, 363\u2013374.","DOI":"10.1016\/B978-0-12-566780-7.50026-X"},{"key":"BF02579169_CR23","unstructured":"M. Stallmann,An Augmenting Paths Algorithm for the Matroid Parity Problem on Binary Matroids, Ph.D. Thesis, University of Colorado at Boulder, 1982."},{"key":"BF02579169_CR24","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan, Efficiency of a good but not linear set union algorithm,J. ACM 22 (1975), 215\u2013225.","journal-title":"J. ACM"},{"key":"BF02579169_CR25","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan,Data Structures and Network Algorithms, SIAM, Philadelphia, PA., 1983."},{"key":"BF02579169_CR26","volume-title":"Matroid Theory","author":"D. J. A. Welsh","year":"1976","unstructured":"D. J. A. Welsh,Matroid Theory, Academic Press, New York, 1976."},{"key":"BF02579169_CR27","doi-asserted-by":"crossref","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H. Whitney","year":"1935","unstructured":"H. Whitney, On the abstract properties of linear dependence,American Journal of Mathematics,57 (1935), 509\u2013533.","journal-title":"American Journal of Mathematics"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579169.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02579169\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02579169","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T16:44:58Z","timestamp":1558197898000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02579169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,6]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1986,6]]}},"alternative-id":["BF02579169"],"URL":"https:\/\/doi.org\/10.1007\/bf02579169","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,6]]}}}