{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T00:27:27Z","timestamp":1704846447764},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,28]],"date-time":"2014-10-28T00:00:00Z","timestamp":1414454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9945-x","type":"journal-article","created":{"date-parts":[[2014,10,27]],"date-time":"2014-10-27T12:02:36Z","timestamp":1414411356000},"page":"270-325","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Fast Algorithms for the Undirected Negative Cost Cycle Detection Problem"],"prefix":"10.1007","volume":"74","author":[{"given":"Matthew","family":"Williamson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavlos","family":"Eirinakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Subramani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,28]]},"reference":[{"key":"9945_CR1","volume-title":"Network Flows: Theory, Algorithms and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"9945_CR2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"RE Bellman","year":"1958","unstructured":"Bellman, R.E.: On a routing problem. Q. Appl. Math. 16, 87\u201390 (1958)","journal-title":"Q. Appl. Math."},{"key":"9945_CR3","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1287\/ijoc.11.2.138","volume":"11","author":"W Cook","year":"1999","unstructured":"Cook, W., Rohe, A.: Computing minimum-weight perfect matchings. INFORMS J. Comput. 11, 138\u2013148 (1999)","journal-title":"INFORMS J. Comput."},{"key":"9945_CR4","doi-asserted-by":"crossref","unstructured":"Cunningham, W.H., Marsh, A.B.: A primal algorithm for optimum matching. In: Polyhedral Combinatorics, pp. 50\u201372. Spring Berlin Heidelberg (1978)","DOI":"10.1007\/BFb0121194"},{"key":"9945_CR5","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.: 9th DIMACS implementation challenge\u2014shortest paths (2005). http:\/\/www.dis.uniroma1.it\/challenge9\/"},{"key":"9945_CR6","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF01594929","volume":"50","author":"U Derigs","year":"1991","unstructured":"Derigs, U., Metz, A.: Solving (large scale) matching problems combinatorially. Math. Program. 50, 113\u2013122 (1991)","journal-title":"Math. Program."},{"key":"9945_CR7","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"key":"9945_CR8","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.L.: Matching, euler tours and the chinese postman problem. Math. Program. 5, 88\u2013124 (1973)","journal-title":"Math. Program."},{"key":"9945_CR9","unstructured":"Edmonds, J., Johnson, E.L., Lockhart, S.C.: Blossom I: a computer code for the matching problem. Unpublished report (1969)"},{"key":"9945_CR10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with $$0,1$$ 0 , 1 vertices. J. Res. Nat. Bureau Stand. 69B, 125\u2013130 (1965)","journal-title":"J. Res. Nat. Bureau Stand."},{"key":"9945_CR11","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"9945_CR12","unstructured":"Edmonds, J.: An introduction to matching. In: Mimeographed Notes, Engineering Summer Conference, The University of Michigan, Ann Arbor, MI (1967)"},{"issue":"6","key":"9945_CR13","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)","journal-title":"Commun. ACM"},{"key":"9945_CR14","first-page":"213","volume-title":"Combinatorics, Paul Erd\u00f6s is Eighty","author":"A Frank","year":"1996","unstructured":"Frank, A.: A survey on $$T$$ T -joins, $$T$$ T -cuts, and conservative weightings. In: Mikl\u00f3s, D., S\u00f3s, V.T., Sz\u00f6nyi, T. (eds.) Combinatorics, Paul Erd\u00f6s is Eighty, vol. 2, pp. 213\u2013252. Bolyai Society, Budapest (1996)"},{"issue":"3","key":"9945_CR15","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"9945_CR16","unstructured":"Gabow, H.: Implementation of algorithms for maximum matching on non-bipartite graphs. PhD Thesis, Stanford University (1974)"},{"key":"9945_CR17","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: A scaling algorithm for weighted matching on general graphs. In: Proceedings of the 26th Annual Symposium of the Foundations of Computer Science. IEEE Computer Society, pp. 90\u2013100 (1985)","DOI":"10.1109\/SFCS.1985.3"},{"key":"9945_CR18","unstructured":"Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms. Association for Computing Machinery, pp. 434\u2013443 (1990)"},{"key":"9945_CR19","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1145\/65950.65954","volume":"36","author":"HN Gabow","year":"1989","unstructured":"Gabow, H.N., Galil, Z., Micali, T.H.: Efficient implementation of graph algorithms using contraction. J. ACM 36, 540\u2013572 (1989)","journal-title":"J. ACM"},{"key":"9945_CR20","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"HN Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM 38, 815\u2013853 (1991)","journal-title":"J. ACM"},{"key":"9945_CR21","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1137\/0215009","volume":"15","author":"Z Galil","year":"1986","unstructured":"Galil, Z., Micali, S., Gabow, H.N.: An $${O}({EV}\\log {V})$$ O ( E V log V ) algorithm for finding a maximal weighted matching in general graphs. SIAM J. Comput. 15, 120\u2013130 (1986)","journal-title":"SIAM J. Comput."},{"key":"9945_CR22","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF01584376","volume":"33","author":"M Gr\u00f6tschel","year":"1985","unstructured":"Gr\u00f6tschel, M., Holland, O.: Solving matching problems with linear programming. Math. Program. 33, 243\u2013259 (1985)","journal-title":"Math. Program."},{"key":"9945_CR23","doi-asserted-by":"crossref","unstructured":"Gu, X., Madduri, K., Subramani, K., Lai, H.-J.: Improved algorithms for detecting negative cost cycles in undirected graphs. In: Deng, X., Hopcroft, J.E., Xe, J. (eds.) Proceedings of the 3rd Annual International Frontiers of Algorithmics Workshop, Lecture Notes in Computer Science, vol. 5598, pp. 40\u201350. Spring Berlin Heidelberg (1999)","DOI":"10.1007\/978-3-642-02270-8_7"},{"key":"9945_CR24","doi-asserted-by":"crossref","unstructured":"Guo, L., Mukhopadhyay, S., Cukic, B.: Does your result checker really check? In: Dependable Systems and Networks, pp. 399\u2013404 (2004)","DOI":"10.1109\/DSN.2004.1311909"},{"key":"9945_CR25","unstructured":"Havel, T.F.: The Combinatorial Distance Geometry Approach to the Calculation of Molecular Conformation. PhD Thesis, University of California, Berkeley (1982)"},{"issue":"1","key":"9945_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"DB Johnson","year":"1977","unstructured":"Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. J. ACM 24(1), 1\u201313 (1977)","journal-title":"J. ACM"},{"key":"9945_CR27","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s12532-009-0002-8","volume":"1","author":"V Kolmogorov","year":"2009","unstructured":"Kolmogorov, V.: Blossom V: a new implementation of a minimum cost perfect matching algorithm. Math. Program. Comput. 1, 43\u201367 (2009). doi: 10.1007\/s12532-009-0002-8","journal-title":"Math. Program. Comput."},{"key":"9945_CR28","unstructured":"Kolmogorov, V.: Implementation of the blossom V algorithm (2009). http:\/\/pub.ist.ac.at\/vnk\/software.html"},{"key":"9945_CR29","volume-title":"Combinatorial Optimization. Number 21 in Algorithms and Combinatorics","author":"B Korte","year":"2010","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization. Number 21 in Algorithms and Combinatorics, 4th edn. Springer, New York (2010)","edition":"4"},{"issue":"2","key":"9945_CR30","first-page":"326","volume":"36","author":"D Kratsch","year":"2006","unstructured":"Kratsch, D., McConnell, R.M., Mehlhorn, K., Spinrad, J.: Certifying algorithms for recognizing interval graphs and permutation graphs SIAM. J. Comput. 36(2), 326\u2013353 (2006)","journal-title":"J. Comput."},{"key":"9945_CR31","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"EL Lawler","year":"1976","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York (1976)"},{"key":"9945_CR32","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. North-Holland, Amsterdam (1986)"},{"key":"9945_CR33","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Sch\u00e4fer, G.: Implementation of $$O(nm\\log n)$$ O ( n m log n ) weighted matchings in general graphs: the powers of data structures. J. Exp. Algorithms 7(4) (2002). doi: 10.1145\/944618.944622","DOI":"10.1145\/944618.944622"},{"key":"9945_CR34","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1287\/ijoc.7.3.298","volume":"7","author":"DL Miller","year":"1995","unstructured":"Miller, D.L., Pekny, J.F.: A staged primal-dual algorithm for perfect $$b$$ b -matching with edge capacities. ORSA J. Comput. 7, 298\u2013320 (1995)","journal-title":"ORSA J. Comput."},{"key":"9945_CR35","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1999","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1999)"},{"key":"9945_CR36","unstructured":"Pulleyblank , W.R.: Faces of Matching Polyhedra. PhD Thesis, University of Waterloo, Waterloo, Ontario (1973)"},{"key":"9945_CR37","doi-asserted-by":"crossref","unstructured":"Shoshan, A., Zwick, U.: All pairs shortest paths in undirected graphs with integer weights. In: IEEE, 40th Annual Symposium on Foundations of Computer Science: October 17\u201319, 1999, New York City, New York, pp. 605\u2013614, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA. IEEE Computer Society Press (1999)","DOI":"10.1109\/SFFCS.1999.814635"},{"issue":"3","key":"9945_CR38","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1016\/j.jda.2006.12.002","volume":"5","author":"K Subramani","year":"2007","unstructured":"Subramani, K.: A zero-space algorithm for negative cost cycle detection in networks. J. Discret. Algorithms 5(3), 408\u2013421 (2007)","journal-title":"J. Discret. Algorithms"},{"key":"9945_CR39","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22, 215\u2013225 (1975)","journal-title":"J. ACM"},{"key":"9945_CR40","unstructured":"Trick, M.: Networks with Additional Structured Constraints. PhD Thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia (1987)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9945-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9945-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9945-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T13:55:10Z","timestamp":1565963710000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9945-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,28]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9945"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9945-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,28]]}}}