{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:37:02Z","timestamp":1725482222481},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540667315"},{"type":"electronic","value":"9783540467847"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46784-x_35","type":"book-chapter","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T08:02:55Z","timestamp":1175760175000},"page":"377-390","source":"Crossref","is-referenced-by-count":2,"title":["On Claw-Free Asteroidal Triple-Free Graphs"],"prefix":"10.1007","author":[{"given":"Harald","family":"Hempel","sequence":"first","affiliation":[]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N. Alon","year":"1997","unstructured":"N. Alon, R. Yuster, and U. Zwick, Finding and counting given length cycles, Algorithmica 17 (1997), 209\u2013223. 381","journal-title":"Algorithmica"},{"key":"35_CR2","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0020-0190(91)90195-N","volume":"37","author":"H. Alt","year":"1991","unstructured":"H. Alt, N. Blum, K. Mehlhorn, and M. Paul, Computing a maximum matching in a bipartite graph in time O(n 1.5\u221am\/log n), Inform. Proc. Lett. 37 (1991), 237\u2013240.","journal-title":"Inform. Proc. Lett."},{"key":"35_CR3","unstructured":"A. Brandst\u00e4dt, Special graph classes \u2014 a survey, Schriftenreihe des Fachbereichs Mathematik, SM-DU-199, Universit\u00e4t Gesamthochschule Duisburg, 1993. 379, 381"},{"key":"35_CR4","unstructured":"A. Brandst\u00e4dt, F. Dragan, and E. K\u00f6hler, Efficient algorithms for Hamiltonian problems on (claw, net)-free graphs, Proc. of WG\u201999, To appear. 378, 378"},{"key":"35_CR5","doi-asserted-by":"crossref","unstructured":"H. Broersma, T. Kloks, D. Kratsch, and H. M\u00fcller, Independent sets in asteroidal triple-free graphs, Proceedings of ICALP\u201997, Springer-Verlag, LNCS 1256, 1997, Berlin, 760\u2013770. 378, 387","DOI":"10.1007\/3-540-63165-8_229"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"D.G. Corneil, F.F. Dragan, M. Habib, and C. Paul, Diameter determination on restricted graph families, Proc. of WG\u201998, Springer-Verlag, LNCS 1517, 1998, 192\u2013202. 378, 378","DOI":"10.1007\/10692760_16"},{"key":"35_CR7","doi-asserted-by":"publisher","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. Dis. Math. 10 (1997), 399\u2013430. 379, 379, 381","journal-title":"SIAM J. Dis. Math."},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"D.G. Corneil, S. Olariu, and L. Stewart, A linear time algorithm for dominating pairs in asteroidal triple-free graphs, Proc. of ICALP\u201995, Springer-Verlag, LNCS 944, 1995, 292\u2013302. 378, 379, 379, 379, 379, 381, 381","DOI":"10.1007\/3-540-60084-1_82"},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"V. Chepoi and F. Dragan, A linear-time algorithm for finding a central vertex of a chordal graph, Proc. of ESA\u201994, Springer-Verlag, 1994, Berlin, LNCS 855, 159\u2013170. 384","DOI":"10.1007\/BFb0049406"},{"key":"35_CR10","unstructured":"V. Chepoi and F. Dragan, Finding a central vertex in HHD-free graphs, Preprint, University of Rostock, 1998. 384"},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"M.J. Fischer and A.R. Meyer, Boolean matrix multiplication and transitive closure, Proc. of the Annual Symposium on Switching and Automata Theory, 1971, 129\u2013131. 384","DOI":"10.1109\/SWAT.1971.4"},{"key":"35_CR12","doi-asserted-by":"publisher","first-page":"701","DOI":"10.2307\/2033375","volume":"7","author":"D.R. Fulkerson","year":"1956","unstructured":"D.R. Fulkerson, Note on Dilworth\u2019s decomposition theorem for partially ordered sets, Proc. Amer. Math. Soc. 7 (1956), 701\u2013702. 388","journal-title":"Proc. Amer. Math. Soc."},{"key":"35_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"R.M. Garey","year":"1979","unstructured":"R.M. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman, San Francisco, 1979. 387"},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980. 379","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"35_CR15","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981), 718\u2013720. 388","journal-title":"SIAM J. Comput."},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"T. Kloks, D. Kratsch, and H. M\u00fcller, Approximating the bandwidth for at-free graphs, Proc. of ESA\u201995, Springer-Verlag, LNCS 979, 1995, 434\u2013447. 378, 378, 381, 381","DOI":"10.1007\/3-540-60313-1_161"},{"key":"35_CR17","unstructured":"D. Kratsch, Domination and total domination on asteroidal triple-free graphs, Forschungsergebnisse Math\/Inf\/96\/25, FSU Jena, Germany, 1996. 378, 387"},{"key":"35_CR18","unstructured":"S. Micali, V.V. Vazirani, An O(V 1\/2 E) algorithm for finding maximum matching in general graphs, Proc. of FOCS\u201980, New York, 1980, 17\u201325. 388"},{"key":"35_CR19","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"G.J. Minty","year":"1980","unstructured":"G.J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Comb. Theory, Ser. B 28 (1980), 284\u2013304. 387","journal-title":"J. Comb. Theory, Ser. B"},{"key":"35_CR20","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0166-218X(97)00041-3","volume":"79","author":"A. Parra","year":"1997","unstructured":"A. Parra and P. Scheffer, Characterizations and algorithmic applications of chordal graph embeddings, Disc. App. Math. 79 (1997), 171\u2013188. 378","journal-title":"Disc. App. Math."},{"key":"35_CR21","doi-asserted-by":"publisher","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. 379, 379","journal-title":"SIAM J. Comput."},{"key":"35_CR22","doi-asserted-by":"crossref","unstructured":"K. Simon, Effiziente Algorithmen f\u00fcr perfekte Graphen, B.G. Teubner, Stuttgart, 1992. 388","DOI":"10.1007\/978-3-322-94768-0"},{"key":"35_CR23","unstructured":"J. Spinrad, private communication. 378, 381, 381, 382"},{"key":"35_CR24","unstructured":"D. West, Introduction to graph theory, Prentice Hall, Upper Saddle River, 1996. 379"}],"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\/3-540-46784-X_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T23:38:18Z","timestamp":1556321898000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46784-X_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540667315","9783540467847"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-46784-x_35","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}