{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T18:57:06Z","timestamp":1778871426596,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540637578","type":"print"},{"value":"9783540696438","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0024501","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T07:30:56Z","timestamp":1132385456000},"page":"229-241","source":"Crossref","is-referenced-by-count":12,"title":["Asteroidal sets in graphs"],"prefix":"10.1007","author":[{"given":"Ton","family":"Kloks","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H. Bodlaender","year":"1995","unstructured":"Bodlaender, H., T. Kloks and D. Kratsch, Treewidth and pathwidth of permutation graphs, SIAM Journal on Discrete Mathematics 8 (1995), pp. 606\u2013616.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"20_CR2","unstructured":"Brandst\u00e4dt, A., Special graph classes-A survey, Schriftenreihe des Fachbereichs Mathematik, SM-DU-199, 1991, Universit\u00e4t Duisburg Gesamthochschule."},{"key":"20_CR3","series-title":"Memorandum No. 1359","volume-title":"Independent sets in asteroidal triple-free graphs","author":"H. Broersma","year":"1996","unstructured":"Broersma, H., T. Kloks, D. Kratsch and H. M\u00fcller, Independent sets in asteroidal triple-free graphs, Memorandum No. 1359, University of Twente, Enschede, The Netherlands, 1996."},{"key":"20_CR4","unstructured":"Corneil, D.G., S. Olariu and L. Stewart, The linear structure of graphs: Asteroidal triple-free graphs. Proceedings of WG'93, Springer-Verlag, LNCS 790, 1994, pp. 211\u2013224; full version to appear in SIAM Journal on Discrete Mathematics."},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Corneil, D.G., S. Olariu and L. Stewart, A linear time algorithm to compute dominating pairs in asteroidal triple-free graphs, Proceedings of ICALP'95, Springer-Verlag, LNCS 944, 1995, pp. 292\u2013302.","DOI":"10.1007\/3-540-60084-1_82"},{"key":"20_CR6","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G. and M.R. Fellows, Fixed-parameter tractability and completeness II: On completeness for W[1], Theoretical Computer Science 141 (1995), pp. 109\u2013131.","journal-title":"Theoretical Computer Science"},{"key":"20_CR7","unstructured":"Eschen, E.M., J.P. Spinrad, An O(n 2) algorithm for circular-arc graph recognition, Proceedings of SODA'93, 1993; pp. 128\u2013137."},{"key":"20_CR8","volume-title":"Algorithmic graph theory and perfect graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C., Algorithmic graph theory and perfect graphs, Academic Press, New York, 1980."},{"key":"20_CR9","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0012-365X(96)00045-3","volume":"164","author":"R. Faudree","year":"1997","unstructured":"Faudree, R., E. Flandrin and Z. Ryj\u00e1\u010dek, Claw-free graphs \u2014 a survey, Discrete Mathematics 164 (1997), pp. 87\u2013147.","journal-title":"Discrete Mathematics"},{"key":"20_CR10","unstructured":"H\u00e5stad, Clique is hard to approximate within n 1\u2212\u025b, in Proceedings of 37th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society (1996), pp. 627\u2013636."},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Kloks, T., Treewidth \u2014 Computations and Approximations, Springer-Verlag, LNCS 842, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"20_CR12","unstructured":"Kloks, T., D. Kratsch and H. M\u00fcller, A generalization of AT-free graphs and some algorithmic results, manuscript, 1996."},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Kloks, T., D. Kratsch and H. M\u00fcller, Finding and counting small induced subgraphs efficiently, Proceedings of WG'95, Springer-Verlag, LNCS 1017, 1995, pp. 14\u201323.","DOI":"10.1007\/3-540-60618-1_62"},{"key":"20_CR14","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C.G. Lekkerkerker","year":"1962","unstructured":"Lekkerkerker, C.G. and J.Ch. Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae 51 (1962), pp. 45\u201364.","journal-title":"Fundamenta Mathematicae"},{"key":"20_CR15","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"G.J. Minty","year":"1980","unstructured":"Minty, G.J., On maximal independent sets of vertices in claw-free graphs, Journal on Combinatorial Theory Series B 28 (1980), pp. 284\u2013304.","journal-title":"Journal on Combinatorial Theory Series B"},{"key":"20_CR16","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0166-218X(95)00095-9","volume":"64","author":"R.H. M\u00f6hring","year":"1996","unstructured":"M\u00f6hring, R.H., Triangulating graphs without asteroidal triples, Discrete Applied Mathematics 64 (1996), pp. 281\u2013287.","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR17","volume-title":"Structural and algorithmic aspects of chordal graph embeddings","author":"A. Parra","year":"1996","unstructured":"Parra, A., Structural and algorithmic aspects of chordal graph embeddings, PhD. thesis, Technische Universit\u00e4t Berlin, 1996."},{"key":"20_CR18","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF02941616","volume":"62","author":"E. Prisner","year":"1992","unstructured":"Prisner, E., Representing triangulated graphs in stars, Abhandlungen des Mathematischen Seminars der Universit\u00e4t Hamburg 62 (1992), pp. 29\u201341.","journal-title":"Abhandlungen des Mathematischen Seminars der Universit\u00e4t Hamburg"},{"key":"20_CR19","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1002\/net.3230120407","volume":"12","author":"D. Rotem","year":"1982","unstructured":"Rotem, D. and J. Urrutia, Circular permutations graphs, Networks 12 (1982), pp. 429\u2013437.","journal-title":"Networks"},{"key":"20_CR20","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N. Sbihi","year":"1980","unstructured":"Sbihi, N., Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile, Discrete Mathematics 29 (1980), pp. 53\u201376.","journal-title":"Discrete Mathematics"},{"key":"20_CR21","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0166-218X(91)90030-Z","volume":"31","author":"A.A. Sch\u00e4ffer","year":"1991","unstructured":"Sch\u00e4ffer, A.A., Recognizing brittle graphs: remarks on a paper of Ho\u00e0ng and Khouzam, Discrete Applied Mathematics 31 (1991), pp. 29\u201335.","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR22","doi-asserted-by":"crossref","unstructured":"Simon, K., Effiziente Algorithmen f\u00fcr perfekte Graphen, B.G. Teubner, Stuttgart, 1992.","DOI":"10.1007\/978-3-322-94768-0"},{"key":"20_CR23","unstructured":"Uehara, R., NP-complete problems on a 3-connected cubic planar graph and their applications, Technical Report TWCU-M-0004, Tokyo Woman's Christian Univ., 1996."},{"key":"20_CR24","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1007\/BF01594196","volume":"14","author":"K. Wagner","year":"1937","unstructured":"Wagner, K., \u00dcber eine Eigenschaft der ebenen Complexe, Mathematische Annalen 14 (1937), pp. 570\u2013590.","journal-title":"Mathematische Annalen"},{"key":"20_CR25","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1002\/jgt.3190020311","volume":"2","author":"J.R. Walter","year":"1978","unstructured":"Walter, J.R., Representations of chordal graphs as subtrees of a tree, Journal of Graph Theory 2 (1978), pp. 265\u2013267.","journal-title":"Journal of Graph Theory"}],"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\/BFb0024501","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T01:35:34Z","timestamp":1586568934000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0024501"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637578","9783540696438"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/bfb0024501","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]}}}