{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:32:53Z","timestamp":1787506373493,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540669166","type":"print"},{"value":"9783540466321","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46632-0_17","type":"book-chapter","created":{"date-parts":[[2007,11,24]],"date-time":"2007-11-24T14:45:01Z","timestamp":1195915501000},"page":"163-172","source":"Crossref","is-referenced-by-count":10,"title":["LexBFS-Ordering in Asteroidal Triple-Free Graphs"],"prefix":"10.1007","author":[{"given":"Jou-Ming","family":"Chang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chin-Wen","family":"Ho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming-Tat","family":"Ko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2000,3,3]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, (series SIAM Monographs on Discrete Mathematics and Applications, 1999).","DOI":"10.1137\/1.9780898719796"},{"key":"17_CR2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13 (1976) 335\u2013379.","journal-title":"J. Comput. System Sci."},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1137\/S0895480197326346","volume":"12","author":"H. Broersma","year":"1999","unstructured":"H. Broersma, T. Kloks, D. Kratsch and H. Muller, Independent sets in asteroidal triple-free graphs, SIAM J. Discrete Math., 12 (1999) 276\u2013287.","journal-title":"SIAM J. Discrete Math."},{"key":"17_CR4","unstructured":"J. M. Chang, C. W. Ho and M. T. Ko, Distances in asteroidal triple-free graphs and their powers, in: Proceedings of CTS Workshop on Combinatorics and Algorithms, Taipei, Taiwan, (1998) 1\u201314."},{"key":"17_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/10692760_16","volume-title":"Proceedings of WG\u201998","author":"D. G. Corneil","year":"1998","unstructured":"D. G. Corneil, F. F. Dragan, M. Habib and C. Paul, Diameter determination on restricted graph families, in: Proceedings of WG\u201998, LNCS Vol. 1517, Springer-Verlag, (1998) 192\u2013202."},{"key":"17_CR6","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0020-0190(95)00021-4","volume":"54","author":"D. G. Corneil","year":"1995","unstructured":"D. G. Corneil, S. Olariu and L. Stewart, A linear time algorithm to compute a dominating path in an AT-free graph, Inform. Process. Lett., 54 (1995) 253\u2013257.","journal-title":"Inform. Process. Lett."},{"key":"17_CR7","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/S0895480193250125","volume":"10","author":"D. G. Corneil","year":"1997","unstructured":"D. G. Corneil, S. Olariu and L. Stewart, Asteroidal triple-free graphs, SIAM J. Discrete Math., 10 (1997), 399\u2013430.","journal-title":"SIAM J. Discrete Math."},{"key":"17_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1007\/3-540-60084-1_82","volume-title":"Proceedings of ICALP\u201995","author":"D. G. Corneil","year":"1995","unstructured":"D. G. Corneil, S. Olariu and L. Stewart, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, in: Proceedings of ICALP\u201995, LNCS Vol. 944, Springer-Verlag, (1995) 292\u2013302."},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hung., 18 (1967) 25\u201366","DOI":"10.1007\/BF02020961"},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0166-218X(84)90016-7","volume":"9","author":"M. C. Golumbic","year":"1984","unstructured":"M. C. Golumbic, C. L. Monma and W. T. Trotter, Jr. Tolerance graphs, Discrete Appl. Math., 9 (1984), 157\u2013170.","journal-title":"Discrete Appl. Math."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"C. T. Ho\u00e0ng and B. A. Reed, P4-comparability graphs, Discrete Math., 74 (1989) 173\u2013200.","DOI":"10.1016\/0012-365X(89)90209-4"},{"key":"17_CR12","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/0196-8858(88)90019-X","volume":"9","author":"B. Jamison","year":"1988","unstructured":"B. Jamison and S. Olariu, On the semi-perfect elimination, Adv. Appl. Math., 9 (1988) 364\u2013376.","journal-title":"Adv. Appl. Math."},{"key":"17_CR13","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/S0304-3975(96)00206-X","volume":"175","author":"T. Kloks","year":"1997","unstructured":"T. Kloks, D. Kratsch and J. Spinrad, On treewidth and minimum fill-in of asteroidal triple-free graphs, Theor. Comput. Sci., 175 (1997) 309\u2013335.","journal-title":"Theor. Comput. Sci."},{"key":"17_CR14","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/S0020-0190(98)00162-8","volume":"68","author":"T. Kloks","year":"1998","unstructured":"T. Kloks. H. M\u00fcller and C. K. Wong, Vertex ranking of asteroidal triple-free graphs, Inform. Process. Lett., 68 (1998) 201\u2013206.","journal-title":"Inform. Process. Lett."},{"key":"17_CR15","volume-title":"Forschungsergebnisse Math\/Inf\/96\/25","author":"D. Kratsch","year":"1996","unstructured":"D. Kratsch, Domination and total domination on asteroidal triple-free graphs, Forschungsergebnisse Math\/Inf\/96\/25, FSU Jena, Germany, 1996."},{"key":"17_CR16","unstructured":"D. Kratsch, H. O. Le, H. M\u00fcller and E. Prisner, Additive tree spanners, manuscript, 1998."},{"key":"17_CR17","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C. G. Lekkerkerker","year":"1962","unstructured":"C. G. Lekkerkerker and J. C. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51 (1962) 45\u201364.","journal-title":"Fund. Math."},{"key":"17_CR18","doi-asserted-by":"crossref","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A. Pnueli","year":"1971","unstructured":"A. Pnueli, A. Lempel and S. Even, Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math., 23 (1971) 160\u2013175.","journal-title":"Canad. J. Math."},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"D, J. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32 (1970) 597\u2013609.","DOI":"10.1016\/0022-247X(70)90282-9"},{"key":"17_CR20","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D. J. Rose","year":"1976","unstructured":"D. J. Rose, R. E. Tarjan and G. S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5 (1976) 266\u2013283.","journal-title":"SIAM J. Comput."},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"J. Spinrad, Transitive orientation in O(n2) time, in: Proceedings of 15th Ann. ACM Symp. on Theory of Computing, (1983) 457\u2013466.","DOI":"10.1145\/800061.808777"},{"key":"17_CR22","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J. Spinrad","year":"1987","unstructured":"J. Spinrad, A. Brandst\u00e4dt and L. Stewart, Bipartite permutation graphs, Discrete Appl. Math., 18 (1987) 279\u2013292.","journal-title":"Discrete Appl. Math."},{"key":"17_CR23","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R. E. Tarjan","year":"1984","unstructured":"R. E. Tarjan and M. Yanakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984) 566\u2013579.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46632-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T22:04:39Z","timestamp":1557007479000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46632-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540669166","9783540466321"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-46632-0_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}