{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:54:20Z","timestamp":1725854060101},"publisher-location":"New York, NY","reference-count":29,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_685","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T18:28:46Z","timestamp":1553106526000},"page":"2291-2297","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Unified View of Graph Searching and LDFS-Based Certifying Algorithms"],"prefix":"10.1007","author":[{"given":"Derek G.","family":"Corneil","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Habib","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"3","key":"450_CR2115","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0020-0190(90)90064-5","volume":"35","author":"SR Arikati","year":"1990","unstructured":"Arikati SR, Rangan CP (1990) Linear algorithm for optimal path cover problem on interval graphs. Inf Process Lett 35(3):149\u2013153","journal-title":"Inf Process Lett"},{"issue":"1\u20133","key":"450_CR2116","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0012-365X(96)00070-2","volume":"171","author":"A Brandst\u00e4dt","year":"1997","unstructured":"Brandst\u00e4dt A, Dragan FF, Nicolai F (1997) LexBFS-orderings and powers of chordal graphs. Discret Math 171(1\u20133):27\u201342","journal-title":"Discret Math"},{"key":"450_CR2117","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes, a survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt A, Le VB, Spinrad JP (1999) Graph classes, a survey. SIAM monographs on discrete mathematics and applications. Society for Industrial and Applied Mathematics, Philadelphia"},{"key":"450_CR2118","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT, Cambridge","edition":"3"},{"key":"450_CR2119","doi-asserted-by":"crossref","unstructured":"Corneil DG (2004) Lexicographic breadth first search \u2013 a survey. In: WG, Bad Honnef. Lecture notes in computer science, vol\u00a03353. Springer, pp\u00a01\u201319","DOI":"10.1007\/978-3-540-30559-0_1"},{"issue":"4","key":"450_CR2120","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/050623498","volume":"22","author":"DG Corneil","year":"2008","unstructured":"Corneil DG, Krueger R (2008) A unified view of graph searching. SIAM J Discret Math 22(4):1259\u20131276","journal-title":"SIAM J Discret Math"},{"issue":"3","key":"450_CR2121","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1137\/11083856X","volume":"42","author":"DG Corneil","year":"2013","unstructured":"Corneil DG, Dalton B, Habib M (2013) LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs. SIAM J Comput 42(3):792\u2013807","journal-title":"SIAM J Comput"},{"key":"450_CR2122","unstructured":"Corneil DG, Dusart J, Habib M, K\u0151hler E (2014) On the power of graph searching for cocomparability graphs. Submitted for publication"},{"key":"450_CR2123","volume-title":"A new model for graph search","author":"DG Corneil","year":"2014","unstructured":"Corneil DG, Dusart J, Habib M, Mamcarz A, de Montgolfier F (2014) A new model for graph search. Under revision"},{"key":"450_CR2124","volume-title":"On minimum path cover in interval graphs","author":"B Dalton","year":"2011","unstructured":"Dalton B (2011) On minimum path cover in interval graphs. Master\u2019s thesis, University of Toronto"},{"issue":"1\u20133","key":"450_CR2125","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0012-365X(93)90223-G","volume":"112","author":"P Damaschke","year":"1993","unstructured":"Damaschke P (1993) Paths in interval graphs and circular arc graphs. Discret Math 112(1\u20133):49\u201364","journal-title":"Discret Math"},{"key":"450_CR2126","unstructured":"Dusart J (2014) Graph searches with applications to cocomparability graphs. PhD thesis, University of Paris Diderot"},{"key":"450_CR2127","first-page":"128","volume":"8","author":"L Euler","year":"1736","unstructured":"Euler L (1736) Solutio problematis ad geometriam situs pertinentis. Comment Academiae Sci I Petropolitanae 8:128\u2013140","journal-title":"Comment Academiae Sci I Petropolitanae"},{"key":"450_CR2128","unstructured":"Fleury (1883) Deux probl\u00e8mes de g\u00e9om\u00e9trie de situation. Journal de math\u00e9matiques \u00e9l\u00e9mentaires 257\u2013261"},{"issue":"4","key":"450_CR2129","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/s00453-013-9752-9","volume":"69","author":"E Gioan","year":"2014","unstructured":"Gioan E, Paul C, Tedder M, Corneil DG (2014) Practical and efficient split-decomposition via graph-labelled trees. Algorithmica 69(4):789\u2013843","journal-title":"Algorithmica"},{"key":"450_CR2130","doi-asserted-by":"crossref","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs. Annals of discrete mathematics, vol\u00a057. Elsevier, Amsterdam\/Boston","DOI":"10.1016\/S0167-5060(04)80059-1"},{"key":"450_CR2131","unstructured":"Habib M, McConnell RM, Paul C, Viennot L (2000) LexBFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor Comput Sci 234(1\u20132):59\u201384. http:\/\/dblp.uni-trier.de\/rec\/bibtex\/journals\/tcs\/HabibMPV00"},{"issue":"2","key":"450_CR2132","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/s00453-010-9411-3","volume":"6","author":"K Ioannidou","year":"2011","unstructured":"Ioannidou K, Mertzios GB, Nikolopoulos SD (2011) The longest path problem has a polynomial solution on interval graphs. Algorithmica 6(2):320\u2013341","journal-title":"Algorithmica"},{"key":"450_CR2133","doi-asserted-by":"crossref","unstructured":"K\u00f6hler E, Mouatadid L (2014) A linear time algorithm for computing a maximum weight independent set on cocomparability graphs. Submitted for publication","DOI":"10.1007\/978-3-319-08404-6_28"},{"key":"450_CR2134","first-page":"319","volume-title":"Linear time LDFS on cocomparability graphs","author":"E K\u00f6hler","year":"2014","unstructured":"K\u00f6hler E, Mouatadid L (2014) Linear time LDFS on cocomparability graphs. In: SWAT, Copenhagen, pp\u00a0319\u2013330"},{"issue":"2\u20133","key":"450_CR2135","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.dam.2010.02.011","volume":"159","author":"R Krueger","year":"2011","unstructured":"Krueger R, Simonet G, Berry A (2011) A general label search to investigate classical graph search algorithms. Discret Appl Math 159(2\u20133):128\u2013142","journal-title":"Discret Appl Math"},{"key":"450_CR2136","volume-title":"R\u00e9cr\u00e9ations math\u00e9matiques","author":"E Lucas","year":"1882","unstructured":"Lucas E (1882) R\u00e9cr\u00e9ations math\u00e9matiques. Gauthier-Vilars, Paris"},{"key":"450_CR2137","unstructured":"Mertzios GB, Corneil DG (2012) A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM J Discret Math 26(3):940\u2013963. http:\/\/dblp.uni-trier.de\/rec\/bibtex\/journals\/siamdm\/MertziosC12"},{"key":"450_CR2138","doi-asserted-by":"crossref","unstructured":"Rose DJ, Tarjan RE, Lueker GS (1976) Algorithmic aspects of vertex elimination on graphs. SIAM J Comput 5(2):266\u2013283. http:\/\/dblp.uni-trier.de\/rec\/bibtex\/journals\/siamcomp\/RoseTL76","DOI":"10.1137\/0205021"},{"key":"450_CR2139","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0166-218X(84)90008-8","volume":"7","author":"DR Shier","year":"1984","unstructured":"Shier DR (1984) Some aspects of perfect elimination orderings in chordal graphs. Discret Appl Math 7:325\u2013331","journal-title":"Discret Appl Math"},{"key":"450_CR2140","unstructured":"Spinrad J (\u2013) Efficient implementation of lexicographic depth first search. Submitted for publication"},{"issue":"2","key":"450_CR2141","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan RE (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1(2):146\u2013160","journal-title":"SIAM J Comput"},{"key":"450_CR2142","first-page":"187","volume":"14","author":"G Tarry","year":"1895","unstructured":"Tarry G (1895) Le probl\u00e8me des labyrinthes. Nouvelles Annales de Math 14:187\u2013189","journal-title":"Nouvelles Annales de Math"},{"key":"450_CR2143","unstructured":"Tedder M (2011) Applications of lexicographic breadth first search to modular decomposition, split decomposition, and circle graphs. PhD thesis, University of Toronto"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,21]],"date-time":"2019-11-21T23:56:20Z","timestamp":1574380580000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_685","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}