{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T14:19:39Z","timestamp":1649081979052},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,5,13]],"date-time":"2014-05-13T00:00:00Z","timestamp":1399939200000},"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":["Optim Lett"],"published-print":{"date-parts":[[2015,2]]},"DOI":"10.1007\/s11590-014-0747-5","type":"journal-article","created":{"date-parts":[[2014,5,11]],"date-time":"2014-05-11T23:27:14Z","timestamp":1399850834000},"page":"345-357","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles"],"prefix":"10.1007","volume":"9","author":[{"given":"M. S.","family":"Ibrahim","sequence":"first","affiliation":[]},{"given":"N.","family":"Maculan","sequence":"additional","affiliation":[]},{"given":"M.","family":"Minoux","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,5,13]]},"reference":[{"key":"747_CR1","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman, R.: On routing problem. Q. Appl. Math. 16, 87\u201390 (1958)","journal-title":"Q. Appl. Math."},{"key":"747_CR2","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":"747_CR3","unstructured":"Ford, L.R., Jr.: Networks flow theory. Paper P-923, The RAND Corporation, Santa Monica, California, [August 14] (1956)"},{"key":"747_CR4","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"747_CR5","volume-title":"Computer and Intractibility: a guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computer and Intractibility: a guide to the theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"747_CR6","volume-title":"Graphes et Algorithmes","author":"M Gondran","year":"1995","unstructured":"Gondran, M., Minoux, M.: Graphes et Algorithmes. Eyrolles, Paris (1995)"},{"key":"747_CR7","doi-asserted-by":"crossref","unstructured":"Hansen, P.: Bicreterion path problems. Multiple criteria decision making: theory and applications, LNEMS 177, pp. 109\u2013127, Springer-verlag, Berlin","DOI":"10.1007\/978-3-642-48782-8_9"},{"key":"747_CR8","unstructured":"Ibrahim, M.S.: Etude de formulations et in\u00e9galit\u00e9s valides pour le probl\u00e8me du plus court chemin dans les graphes avec des circuits absorbants. PhD dissertation, Universit\u00e9 Pierre et Marie Curie, Paris 6 (2007)"},{"key":"747_CR9","first-page":"361","volume":"16","author":"MS Ibrahim","year":"2009","unstructured":"Ibrahim, M.S., Maculan, N., Minoux, M.: Strong flow-based formulation for the shortest path problem in digraphs with negative cycles. ITOR 16, 361\u2013369 (2009)","journal-title":"ITOR"},{"key":"747_CR10","unstructured":"Di Puglia Pugliese, L., Guerriero, F.: On the shortest path problem with negative cost cycles. Technical Report n 5\/10, 2010, LOGICA Laboratory, University of Calabria, Italy (2010)"},{"key":"747_CR11","first-page":"361","volume":"6","author":"PN Klein","year":"2010","unstructured":"Klein, P.N., Mozes, S., Weimann, O.: Shortest paths in directed planar graphs with negative lengths: A linear space $$O(nlog^2 n)$$ O ( n l o g 2 n ) -time algorithm. ACM Trans. Algorithms (TALG) 6, 361\u2013369 (2010)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"747_CR12","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R Lipton","year":"1979","unstructured":"Lipton, R., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal. 16, 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"issue":"2","key":"747_CR13","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R Lipton","year":"1979","unstructured":"Lipton, R., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"key":"747_CR14","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1590\/S0101-74382003000100012","volume":"23","author":"N Maculan","year":"2003","unstructured":"Maculan, N., Plateau, G., Lisser, A.: Integer linear models with a polynomial number of variables and constraints for some classical combinatorial optimization problems. Pesquisa Oper. 23, 161\u2013168 (2003)","journal-title":"Pesquisa Oper."},{"key":"747_CR15","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/S0020-0190(01)00242-3","volume":"81","author":"K Mehlhorn","year":"2002","unstructured":"Mehlhorn, K., Priebe, V., Schafer, G., Sivadasan, N.: All-pairs shortest paths computation in the presence of negative cycles. Inf. Process. Lett. 81, 341\u2013343 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"747_CR16","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"GL Miller","year":"1986","unstructured":"Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. System Sci. 32(3), 265\u2013279 (1986)","journal-title":"J. Comput. System Sci."},{"key":"747_CR17","unstructured":"Minoux, M.: Programmation math\u00e9matique. $$2^e$$ 2 e \u00e9dition Lavoisier (2008)"},{"key":"747_CR18","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, 408\u2013421 (2007)","journal-title":"J. Discret. Algorithms"},{"issue":"4","key":"747_CR19","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/j.future.2004.09.001","volume":"21","author":"K Subramani","year":"2005","unstructured":"Subramani, K., Kovalchick, L.: A greedy strategy for detecting negative cost cycles in networks. Future Gener. Comput. Systems 21(4), 607\u2013623 (2005)","journal-title":"Future Gener. Comput. Systems"},{"key":"747_CR20","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0166-218X(01)00201-3","volume":"118","author":"T Yamada","year":"2002","unstructured":"Yamada, T., Kinoshita, H.: Finding all the negative cycles in a directedgraph. Discret. Appl. Math. 118, 279\u2013291 (2002)","journal-title":"Discret. Appl. Math."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-014-0747-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-014-0747-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-014-0747-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T06:55:55Z","timestamp":1565420155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-014-0747-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,13]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["747"],"URL":"https:\/\/doi.org\/10.1007\/s11590-014-0747-5","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,13]]}}}