{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:44:42Z","timestamp":1759063482354},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540204527"},{"type":"electronic","value":"9783540398905"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39890-5_11","type":"book-chapter","created":{"date-parts":[[2010,9,4]],"date-time":"2010-09-04T01:16:57Z","timestamp":1283563017000},"page":"119-130","source":"Crossref","is-referenced-by-count":19,"title":["A Simple Linear Time LexBFS Cograph Recognition Algorithm"],"prefix":"10.1007","author":[{"given":"Anna","family":"Bretscher","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Derek","family":"Corneil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"Habib","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","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":"11_CR2","doi-asserted-by":"crossref","unstructured":"Corneil, D.G.: A Simple 3-sweep LBFS Algorithm for the Recognition of Unit Interval Graphs. Discrete AppliedMathematics (to appear)","DOI":"10.1016\/j.dam.2003.07.001"},{"key":"11_CR3","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.K.: The Ultimate Interval Graph Recognition Algorithm (Extended Abstract). In: Symposium on Discrete Algorithms, pp. 175\u2013180 (1998)"},{"issue":"1","key":"11_CR4","first-page":"63","volume":"3","author":"D.G. Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Stewart Burlingham, L.: Complement Reducible Graphs. Discrete Applied Math.\u00a03(1), 63\u2013174 (1981)","journal-title":"Discrete Applied Math."},{"issue":"4","key":"11_CR5","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D.G. Corneil","year":"1985","unstructured":"Corneil, D.G., Pearl, Y., Stewart, L.: A linear recognition algorithm for cographs. SIAM Journal of Computing\u00a014(4), 926\u2013934 (1985)","journal-title":"SIAM Journal of Computing"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/BFb0017474","volume-title":"Trees in Algebra and Programming - CAAP \u201994","author":"A. Cournier","year":"1994","unstructured":"Cournier, A., Habib, M.: A new linear algorithm for modular decomposition. In: Tison, S. (ed.) CAAP 1994. LNCS, vol.\u00a0787, pp. 68\u201384. Springer, Heidelberg (1994)"},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(93)E0138-O","volume":"57","author":"E. Dahlhaus","year":"1995","unstructured":"Dahlhaus, E.: Efficient parallel recognition algorithms for cographs andd istance hereditary graphs. Discrete Applied Mathematics\u00a057, 29\u201345 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR8","unstructured":"Dahlhaus, E., Gustedt, J., McConnell, R.M.: Efficient andpractical modular decomposition. In: 8th Annual ACM-SIAM Symposium On Discrete Algorithms (SODA), pp. 26\u201335 (1997)"},{"key":"11_CR9","unstructured":"Habib, M., Paul, C.: A new vertex splitting algorithm for cograph recognition. Technical Report (April 2000), \n                    \n                      http:\/\/citeseer.nj.nec.com\/habib00new.html"},{"key":"11_CR10","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.M., Paul, C., Viennot, L.: Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition and Consecutive Ones Testing. Theoretical Computer Science\u00a0234, 59\u201384 (2000)","journal-title":"Theoretical Computer Science"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0218005","volume":"18","author":"N. Korte","year":"1989","unstructured":"Korte, N., M\u00f6hring, H.: An incremental linear-time algorithm for recognizing interval graphs. SIAM J. Comput.\u00a018, 68\u201381 (1989)","journal-title":"SIAM J. Comput."},{"key":"11_CR12","unstructured":"McConnell, R.M., Spinrad, J.: Linear-Time Modular Decomposition and Efficient Transitive Orientation of Comparability Graphs. In: Proceedings of the ACMSIAM Symposium on Discrete Algorithms, pp. 536\u2013545 (1994)"},{"key":"11_CR13","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":"11_CR14","unstructured":"Shew, S.: A Cograph Approach to Examination Scheduling. M.Sc Thesis, Dept. of Computer Science, University of Toronto (1986)"},{"key":"11_CR15","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddler River (2001)","edition":"2"}],"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-39890-5_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T21:43:38Z","timestamp":1553031818000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39890-5_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540204527","9783540398905"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39890-5_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}