{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T09:10:22Z","timestamp":1779268222513,"version":"3.51.4"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T00:00:00Z","timestamp":1557878400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T00:00:00Z","timestamp":1557878400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2021,10]]},"DOI":"10.1007\/s10878-019-00416-y","type":"journal-article","created":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T19:46:17Z","timestamp":1557949577000},"page":"476-498","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Tropical paths in vertex-colored graphs"],"prefix":"10.1007","volume":"42","author":[{"given":"Johanne","family":"Cohen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yannis","family":"Manoussakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nguyen Kim","family":"Thang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2238-8865","authenticated-orcid":false,"given":"Hong Phong","family":"Pham","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,15]]},"reference":[{"issue":"1","key":"416_CR1","doi-asserted-by":"publisher","first-page":"P17","DOI":"10.37236\/504","volume":"18","author":"S Akbari","year":"2011","unstructured":"Akbari S, Liaghat V, Nikzad A (2011) Colorful paths in vertex coloring of graphs. Electron J Comb 18(1):P17","journal-title":"Electron J Comb"},{"key":"416_CR2","doi-asserted-by":"crossref","unstructured":"Angles\u00a0d\u2019Auriac JA, Bujt\u00e1s C, El\u00a0Maftouhi H, Narayanan N, Rosaz L, Thapper J, Tuza Z (2016) Tropical dominating sets in vertex-coloured graphs. In: Proceedings of 10th workshop on algorithms and computation (WALCOM), vol 9627, p 17","DOI":"10.1007\/978-3-319-30139-6_2"},{"issue":"2","key":"416_CR3","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0020-0190(83)90078-9","volume":"17","author":"AA Bertossi","year":"1983","unstructured":"Bertossi AA (1983) Finding hamiltonian circuits in proper interval graphs. Inf Process Lett 17(2):97\u2013101","journal-title":"Inf Process Lett"},{"key":"416_CR4","doi-asserted-by":"crossref","unstructured":"Bruckner S, H\u00fcffner F, Komusiewicz C, Niedermeier R (2013) Evaluation of ilp-based approaches for partitioning into colorful components. In: International symposium on experimental algorithms, pp 176\u2013187","DOI":"10.1007\/978-3-642-38527-8_17"},{"key":"416_CR5","doi-asserted-by":"crossref","unstructured":"Cohen J, Manoussakis Y, Pham H, Tuza Z (2017 (to appear)) Tropical matchings in vertex-colored graphs. In: Latin and American algorithms, graphs and optimization symposium","DOI":"10.1007\/978-3-319-71147-8_20"},{"issue":"8","key":"416_CR6","doi-asserted-by":"publisher","first-page":"1015","DOI":"10.1093\/bioinformatics\/btq082","volume":"26","author":"E Corel","year":"2010","unstructured":"Corel E, Pitschi F, Morgenstern B (2010) A min-cut algorithm for the consistency problem in multiple sequence alignment. Bioinformatics 26(8):1015\u20131021","journal-title":"Bioinformatics"},{"issue":"4","key":"416_CR7","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1016\/j.jcss.2010.07.003","volume":"77","author":"MR Fellows","year":"2011","unstructured":"Fellows MR, Fertin G, Hermelin D, Vialette S (2011) Upper and lower bounds for finding connected motifs in vertex-colored graphs. J Comput Syst Sci 77(4):799\u2013811","journal-title":"J Comput Syst Sci"},{"key":"416_CR8","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.dam.2017.04.027","volume":"229","author":"F Foucaud","year":"2017","unstructured":"Foucaud F, Harutyunyan A, Hell P, Legay S, Manoussakis Y, Naserasr R (2017) Tropical homomorphisms in vertex-coloured graphs. Discret Appl Math 229:64\u201381","journal-title":"Discret Appl Math"},{"issue":"4","key":"416_CR9","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad J (2001) Some optimal inapproximability results. J ACM (JACM) 48(4):798\u2013859","journal-title":"J ACM (JACM)"},{"key":"416_CR10","doi-asserted-by":"crossref","unstructured":"Ioannidou K, Mertzios GB, Nikolopoulos SD (2009) The longest path problem is polynomial on interval graphs. In: Symposium on mathematical foundations of computer science (MFCS), vol 5734, pp 403\u2013414","DOI":"10.1007\/978-3-642-03816-7_35"},{"issue":"1","key":"416_CR11","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/BF02523689","volume":"18","author":"D Karger","year":"1997","unstructured":"Karger D, Motwani R, Ramkumar G (1997) On approximating the longest path in a graph. Algorithmica 18(1):82\u201398","journal-title":"Algorithmica"},{"issue":"4","key":"416_CR12","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/PL00007256","volume":"17","author":"H Li","year":"2001","unstructured":"Li H (2001) A generalization of the gallai-roy theorem. Gr Comb 17(4):681\u2013685","journal-title":"Gr Comb"},{"issue":"2","key":"416_CR13","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00373-007-0694-3","volume":"23","author":"C Lin","year":"2007","unstructured":"Lin C (2007) Simple proofs of results on paths representing all colors in proper vertex-colorings. Gr Comb 23(2):201\u2013203","journal-title":"Gr Comb"},{"issue":"1\u20132","key":"416_CR14","first-page":"11","volume":"48","author":"D Marx","year":"2004","unstructured":"Marx D (2004) Graph colouring problems and their applications in scheduling. Periodica Polytech Electr Eng 48(1\u20132):11\u201316","journal-title":"Periodica Polytech Electr Eng"},{"key":"416_CR15","doi-asserted-by":"crossref","unstructured":"Micali S, Vazirani VV (1980) An $${O}(\\sqrt{|V|} |{E}|)$$ algorithm for finding maximum matching in general graphs. In: Proceedings of 21st symposium on foundations of computer science, pp 17\u201327","DOI":"10.1109\/SFCS.1980.12"},{"key":"416_CR16","doi-asserted-by":"crossref","unstructured":"Uehara R, Uno Y (2004) Efficient algorithms for the longest path problem. In: International symposium on algorithms and computation, pp 871\u2013883","DOI":"10.1007\/978-3-540-30551-4_74"},{"issue":"2","key":"416_CR17","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.ipl.2007.02.010","volume":"103","author":"R Uehara","year":"2007","unstructured":"Uehara R, Valiente G (2007) Linear structure of bipartite permutation graphs and the longest path problem. Inf Process Lett 103(2):71\u201377","journal-title":"Inf Process Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00416-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-019-00416-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00416-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T06:30:35Z","timestamp":1635575435000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-019-00416-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,15]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["416"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00416-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,15]]},"assertion":[{"value":"15 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}