{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:14:30Z","timestamp":1781345670462,"version":"3.54.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1996,9,1]],"date-time":"1996-09-01T00:00:00Z","timestamp":841536000000},"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":[[1996,9]]},"DOI":"10.1007\/bf01261321","type":"journal-article","created":{"date-parts":[[2005,3,23]],"date-time":"2005-03-23T22:01:48Z","timestamp":1111615308000},"page":"353-382","source":"Crossref","is-referenced-by-count":24,"title":["Path problems in skew-symmetric graphs"],"prefix":"10.1007","volume":"16","author":[{"given":"Andrew V.","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander V.","family":"Karzanov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","unstructured":"R. K. Ahuja, K. Mehlhorn, J. B. Orlin, andR. E. Tarjan: Faster Algorithms for the Shortest Path Problem,Technical Report CS-TR-154-88, Department of Computer Science, Princeton University, 1988."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R. E. Bellman","year":"1958","unstructured":"R. E. Bellman: On a Routing Problem,Quart. Appl. Math. 16 (1958), 87?90.","journal-title":"Quart. Appl. Math."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"842","DOI":"10.1073\/pnas.43.9.842","volume":"43","author":"C. Berge","year":"1957","unstructured":"C. Berge: Two Theorems in Graph Theory,Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 842?844.","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"key":"CR4","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson, andR. L. Rivest:Introduction to Algorithms, (MIT Press, Cambridge, MA, 1990)."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra: A Note on Two Problems in Connection with Graphs,Numer. Math. 1 (1959), 269?271.","journal-title":"Numer. Math."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"96B","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds: Maximum Matchings and a Polyhedron with 0,1-vertices,J. Res. Nat. Bur. Stand. 96B (1965), 125?130.","journal-title":"J. Res. Nat. Bur. Stand."},{"key":"CR7","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,Canada J. Math. 17 (1965), 449?467.","journal-title":"Canada J. Math."},{"key":"CR8","first-page":"89","volume-title":"Combinatorial Structures and Their Applications","author":"J. Edmonds","year":"1970","unstructured":"J. Edmonds, andE. L. Johnson: Matching, a Well-Solved Class of Integer Linear Programs, In: R. Guy, H. Haneni, and J. Sch\ufffdnhein, editors,Combinatorial Structures and Their Applications (Gordon and Breach, NY, 1970), 89?92."},{"key":"CR9","volume-title":"Flows in Networks","author":"L. R. Ford Jr.","year":"1962","unstructured":"L. R. Ford, Jr., andD. R. Fulkerson:Flows in Networks (Princeton Univ. Press, Princeton, NJ, 1962)."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman, andR. E. Tarjan: Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms,J. Assoc. Comput. Mach. 34 (1987), 596?615.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1109\/TSE.1976.233819","volume":"2","author":"H. N. Gabow","year":"1976","unstructured":"H. N. Gabow, S. N. Maheshwari, andL. Osterweil: On Two Problems in the Generation of Program Test Paths,IEEE Trans. on Software Eng. SE-2 (1976), 227?231.","journal-title":"IEEE Trans. on Software Eng. SE"},{"key":"CR12","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. Comp. and Syst. Sci. 30 (1985), 209?221.","journal-title":"J. Comp. and Syst. Sci."},{"key":"CR13","unstructured":"A. V. Goldberg: Scaling Algorithms for the Shortest Paths Problem, In:Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, 1993, 222?231."},{"key":"CR14","series-title":"Technical Report","volume-title":"Maximum Flows in Skew-Symmetric Graphs","author":"A. V. Goldberg","year":"1995","unstructured":"A. V. Goldberg, andA. V. Karzanov: Maximum Flows in Skew-Symmetric Graphs,Technical Report (Stanford University, Stanford, 1995)."},{"key":"CR15","unstructured":"A. V. Goldberg, andA. V. Karzanov: Minimum Cost Flows in Skew-Symmetric Graphs, in preparation."},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"M. Gr\ufffdtschel, L. Lov\ufffdsz, andA. Schrijver:Geometric Algorithms and Combinatorial Optimization (Springer Verlag, 1988).","DOI":"10.1007\/978-3-642-97881-4"},{"key":"CR17","first-page":"126","volume-title":"Studies in Applied Graph Theory","author":"A. V. Karzanov","year":"1986","unstructured":"A. V. Karzanov: An algorithm for determining a maximum packing of oddterminus cuts and its applications, in:Studies in Applied Graph Theory (A. S. Alekseev, ed., Nauka, Novosibirsk, 1986), 126?140; in Russian; English translation inAmer. Math. Soc. Translations, Ser. 2,158 (1994), 57?70."},{"key":"CR18","first-page":"138","volume-title":"Combinatorial Methods for Flow Problems","author":"A. V. Karzanov","year":"1979","unstructured":"A. V. Karzanov: A Minimum Cost Maximum Multiflow Problem, In:Combinatorial Methods for Flow Problems (Inst. for Systems Studies, Moscow, volume 4, 1979), 138?156; In Russian."},{"issue":"3","key":"CR19","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/BF01581152","volume":"66","author":"A. V. Karzanov","year":"1994","unstructured":"A. V. Karzanov: Minimum Cost Multiflows in Undirected Networks,Mathematical Programming 66 (3) (1994), 313?325.","journal-title":"Mathematical Programming"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01889919","volume":"23","author":"L. Lov\ufffdsz","year":"1972","unstructured":"L. Lov\ufffdsz: The Factorization of Graphs II,Acta Math. Hung. 23 (1972), 223?246.","journal-title":"Acta Math. Hung."},{"key":"CR21","volume-title":"Matching Theory","author":"L. Lov\ufffdsz","year":"1986","unstructured":"L. Lov\ufffdsz, andM. D. Plummer:Matching Theory (Akad\ufffdmiai Kiad\ufffd, Budapest, 1986)."},{"key":"CR22","unstructured":"E. F. Moore: The Shortest Path Through a Maze, In:Proc. of the Int. Symp. on the Theory of Switching (Harvard University Press, 1959), 285?292."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"1975","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. Assoc. Comput. Mach. 22 (1975), 1975.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"W. T. Tutte","year":"1947","unstructured":"W. T. Tutte: The Factorization of Linear Graphs,J. London Math. Soc. 22 (1947), 107?111.","journal-title":"J. London Math. Soc."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.4153\/CJM-1967-101-8","volume":"19","author":"W. T. Tutte","year":"1967","unstructured":"W. T. Tutte: Antisymmetrical Digraphs,Canada J. Math. 19 (1967), 1101?1117.","journal-title":"Canada J. Math."},{"key":"CR26","unstructured":"H. Yinnone: On Paths Avoiding Forbidden Pairs of Vertices in a Graph, submitted toDiscrete Appl. Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01261321.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01261321\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01261321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T12:37:48Z","timestamp":1586176668000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01261321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["BF01261321"],"URL":"https:\/\/doi.org\/10.1007\/bf01261321","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}