{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:31Z","timestamp":1725558931579},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241324"},{"type":"electronic","value":"9783540305590"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30559-0_1","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T19:01:42Z","timestamp":1278097302000},"page":"1-19","source":"Crossref","is-referenced-by-count":19,"title":["Lexicographic Breadth First Search \u2013 A Survey"],"prefix":"10.1007","author":[{"given":"Derek G.","family":"Corneil","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"H.-K. Bandelt","year":"1986","unstructured":"Bandelt, H.-K., Mulder, H.M.: Distance-hereditary graphs. J. Combin. Theory B\u00a041, 182\u2013208 (1986)","journal-title":"J. Combin. Theory B"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0166-218X(98)00005-5","volume":"84","author":"A. Berry","year":"1998","unstructured":"Berry, A., Bordat, J.-P.: Separability generalizes Dirac\u2019s theorem. Disc. Appl. Math.\u00a084, 43\u201353 (1998)","journal-title":"Disc. Appl. Math."},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. System Sci."},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0166-218X(02)00571-1","volume":"129","author":"A. Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Dragan, F.F.: On linear and circular structure of a (claw,net)- free graph. Disc. Appl. Math.\u00a0129, 285\u2013303 (2003)","journal-title":"Disc. Appl. Math."},{"key":"1_CR5","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, F.F., Nicolai, F.: LexBFS-orderings and powers of chordal graphs. Disc. Math.\u00a0171, 27\u201342 (1997)","journal-title":"Disc. Math."},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Disc. Math. and Applic., SIAM (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"1_CR7","unstructured":"Bretscher, A.: LexBFS based recognition algorithms for cographs and related families, Ph.D. thesis in preparation, Dept. of Computer Science, University of Toronto, oronto, Canada"},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-540-39890-5_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Bretscher","year":"2003","unstructured":"Bretscher, A., Corneil, D.G., Habib, M., Paul, C.: A simple linear time lexBFS cograph recognition algorithm. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 119\u2013130. Springer, Heidelberg (2003)"},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/3-540-46632-0_17","volume-title":"Algorithms and Computations","author":"J.-M. Chang","year":"1999","unstructured":"Chang, J.-M., Ho, C.-W., Ko, M.-T.: LexBFS-ordering in asteroidal triple-free graphs. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol.\u00a01741, pp. 163\u2013172. Springer, Heidelberg (1999)"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0378-1119(03)00825-4","volume":"320","author":"V. Choi","year":"2003","unstructured":"Choi, V., Farach-Colton, M.: Barnacle: an assembly algorithm for clone-based sequences of whole genomes. Gene\u00a0320, 165\u2013176 (2003)","journal-title":"Gene"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.dam.2003.07.001","volume":"138","author":"D.G. Corneil","year":"2004","unstructured":"Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Disc. Appl. Math.\u00a0138, 371\u2013379 (2004)","journal-title":"Disc. Appl. Math."},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0166-218X(00)00281-X","volume":"113","author":"D.G. Corneil","year":"2001","unstructured":"Corneil, D.G., Dragan, F.F., Habib, M., Paul, C.: Diameter determination on restricted graph families. Disc. Appl. Math.\u00a0113, 143\u2013166 (2001)","journal-title":"Disc. Appl. Math."},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/net.10098","volume":"42","author":"D.G. Corneil","year":"2003","unstructured":"Corneil, D.G., Dragan, F.F., Koehler, E.: On the power of BFS to determine a graph\u2019s diameter. Networks\u00a042, 209\u2013222 (2003)","journal-title":"Networks"},{"key":"1_CR14","unstructured":"Corneil, D.G., Koehler, E.: unpublished manuscript"},{"key":"1_CR15","unstructured":"Corneil, D.G., Koehler, E., Lanlignel, J.-M.: On LBFS end-vertices (in preparation)"},{"key":"1_CR16","unstructured":"Corneil, D.G., Krueger, R.: A unified view of graph searching (in preparation)"},{"key":"1_CR17","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: The LBFS structure and recognition of interval graphs, under revision; extended abstract appeared as The ultimate interval graph recognition algorithm? (extended abstract). In: Proc. SODA 1998. Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.175\u2013180 (1998)"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"1284","DOI":"10.1137\/S0097539795282377","volume":"28","author":"D.G. Corneil","year":"1999","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Linear time algorithms for dominating pairs in asteroidal triple-free graphs. SIAM J. Comput.\u00a028, 1284\u20131297 (1999)","journal-title":"SIAM J. Comput."},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0166-218X(99)00077-3","volume":"95","author":"F.F. Dragan","year":"1999","unstructured":"Dragan, F.F.: Almost diameter of a house-hole-free graph in linear time via LexBFS. Disc. Appl. Math.\u00a095, 223\u2013239 (1999)","journal-title":"Disc. Appl. Math."},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/3-540-45477-2_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F.F. Dragan","year":"2001","unstructured":"Dragan, F.F.: Estimating all pairs shortest paths in restricted graph families: A unified approach. In: Brandst\u00e4dt, A., Van Le, B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 103-116. Springer, Heidelberg (2001)"},{"key":"1_CR21","unstructured":"Dragan, F.F., Nicolai, F.: Lex-BFS-orderings of distance-hereditary graphs, Schriftenreihe des Fachbereichs Mathematik der Universit\u00e4t Duisburg, Duisburg, Germany, SM-DU-303 (1995)"},{"key":"1_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1007\/3-540-62559-3_15","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F.F. Dragan","year":"1997","unstructured":"Dragan, F.F., Nicolai, F., Brandst\u00e4dt, A.: LexBFS-orderings and powers of graphs. In: D\u2019Amore, F., Marchetti-Spaccamela, A., Franciosa, P.G. (eds.) WG 1996. LNCS, vol.\u00a01197, pp. 166\u2013180. Springer, Heidelberg (1997)"},{"key":"1_CR23","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific J. Math.\u00a015, 835\u2013855 (1965)","journal-title":"Pacific J. Math."},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M. Habib","year":"2000","unstructured":"Habib, M., McConnell, R., Paul, C., Viennot, L.: Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoret. Comput. Sci.\u00a0234, 59\u201384 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Hell, P., Huang, J.: Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs. SIAM J. Disc. Math (2004) (To appear)","DOI":"10.1137\/S0895480103430259"},{"key":"1_CR26","first-page":"705","volume-title":"1988 International Kalamazoo Graph Theory Conference","author":"M.S. Jacobson","year":"1991","unstructured":"Jacobson, M.S., McMorris, F.R., Mulder, H.M.: Tolerance intersection graphs. In: Alavi, Y., et al. (eds.) 1988 International Kalamazoo Graph Theory Conference, pp. 705\u2013724. Wiley, Chichester (1991)"},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1016\/0196-8858(88)90019-X","volume":"9","author":"B. Jamison","year":"1988","unstructured":"Jamison, B., Olariu, S.: On the semi-perfect elimination. Advances in Appl. Math.\u00a09, 364\u2013376 (1988)","journal-title":"Advances in Appl. Math."},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1137\/0406032","volume":"6","author":"D. Kratsch","year":"1993","unstructured":"Kratsch, D., Stewart, L.: Domination on cocomparability graphs. SIAM J. Disc. Math.\u00a06, 400\u2013417 (1993)","journal-title":"SIAM J. Disc. Math."},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0218005","volume":"18","author":"N. Korte","year":"1989","unstructured":"Korte, N., M\u00f6hring, R.H.: An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Comput.\u00a018, 68\u201381 (1989)","journal-title":"SIAM J. Comput."},{"key":"1_CR30","unstructured":"Lanlignel, J.-M.: Private communications (1999)"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0898-1221(93)90308-I","volume":"25","author":"P.J. Looges","year":"1993","unstructured":"Looges, P.J., Olariu, S.: Optimal greedy algorithms for indifference graphs. Computers Math. Applic.\u00a025, 15\u201325 (1993)","journal-title":"Computers Math. Applic."},{"key":"1_CR32","unstructured":"Ma, T.: unpublished manuscript"},{"key":"1_CR33","unstructured":"McConnell, R.M., Spinrad, J.: Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In: Proc. SODA 1994, Fifth Annual ACMSIAM Symposium on Discrete Algorithms, pp. 536\u2013545 (1994)"},{"key":"1_CR34","unstructured":"Meister, D.: Recognizing and computing minimal triangulations efficiently, Technical Report 302, Fakul\u00e4t f\u00fcr Mathematik und Informatik, Universit\u00e4t W\u00fcrzburg (2002)"},{"key":"1_CR35","unstructured":"Nicolai, F.: A hypertree characterization of distance-hereditary graphs, manuscript, Gerhard-Mercator-Universit\u00e4t Duisburg (1996)"},{"key":"1_CR36","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0020-0190(91)90245-D","volume":"37","author":"S. Olariu","year":"1991","unstructured":"Olariu, S.: An optimal greedy heuristic to color interval graphs. Inform. Process. Lett.\u00a037, 65\u201380 (1991)","journal-title":"Inform. Process. Lett."},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0020-0190(88)90091-9","volume":"27","author":"G. Ramalingam","year":"1988","unstructured":"Ramalingam, G., Pandu Rangan, C.: A uniform approach to domination problems on interval graphs. Inform. Process. Lett.\u00a027, 271\u2013274 (1988)","journal-title":"Inform. Process. Lett."},{"key":"1_CR38","first-page":"235","volume":"59","author":"A. Raychaudhuri","year":"1987","unstructured":"Raychaudhuri, A.: On powers of interval and unit interval graphs. Congr. Numer.\u00a059, 235\u2013242 (1987)","journal-title":"Congr. Numer."},{"key":"1_CR39","first-page":"139","volume-title":"Proof Techniques in Graph Theory","author":"F.S. Roberts","year":"1969","unstructured":"Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory, pp. 139\u2013146. Academic Press, New York (1969)"},{"key":"1_CR40","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/0095-8956(71)90010-4","volume":"11","author":"F.S. Roberts","year":"1971","unstructured":"Roberts, F.S.: On the compatibility between a graph and a simple order. J. Combin. Theory Ser. B\u00a011, 28\u201338 (1971)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1_CR41","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comput.\u00a01, 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"1_CR42","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.\u00a05, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"1_CR43","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput.\u00a013, 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"key":"1_CR44","first-page":"289","volume":"553","author":"K. Simon","year":"1992","unstructured":"Simon, K.: A new simple linear algorithm to recognize interval graphs. LNCS 553, 289\u2013308 (1992)","journal-title":"LNCS"},{"key":"1_CR45","unstructured":"Wegner, G.: Eigenschaften der Nerven homologisch-einfacher Familien in R n , Ph.D. thesis, Universit\u00e4t G\u00f6ttigen, Germany (1967)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30559-0_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:22:17Z","timestamp":1605759737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30559-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241324","9783540305590"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30559-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}