{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:23:25Z","timestamp":1725665005174},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540631651"},{"type":"electronic","value":"9783540691945"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63165-8_229","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:12:18Z","timestamp":1330279938000},"page":"760-770","source":"Crossref","is-referenced-by-count":4,"title":["Independent sets in asteroidal triple-free graphs"],"prefix":"10.1007","author":[{"given":"Hajo","family":"Broersma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ton","family":"Kloks","sequence":"additional","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,8]]},"reference":[{"key":"71_CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., D. G. Corneil and A. Proskurowski, Complexity of finding embeddings in a k-tree, SIAMJ. Alg. Disc. Meth. 8 (1987), pp. 277\u2013284.","journal-title":"SIAMJ. Alg. Disc. Meth."},{"key":"71_CR2","unstructured":"Brandst\u00e4dt, A., Special graph classes-A survey, Schriftenreihe des Fachbereichs Mathematik, SM-DU-199, Universit\u00e4t Duisburg Gesamthochschule, 1991."},{"key":"71_CR3","series-title":"Memorandum No. 1359","volume-title":"Independent sets in asteroidal triple-free graphs","author":"H. J. Broersma","year":"1996","unstructured":"Broersma, H. J., T. Kloks, D. Kratsch and H. M\u00fcller, Independent sets in asteroidal triple-free graphs, Memorandum No. 1359, Faculty of Applied Mathematics, University of Twente, Enschede, The Netherlands, 1996."},{"key":"71_CR4","unstructured":"Breu, H. and D. G. Kirkpatrick, Algorithms for domination and Steiner tree problems in cocomparability graphs, Manuscript 1993."},{"key":"71_CR5","doi-asserted-by":"crossref","unstructured":"Chang, M. S., Weighted domination on cocomparability graphs, Proceedings of ISAAC'95, Springer-Verlag, LNCS 1004, 1996, pp. 122\u2013131.","DOI":"10.1007\/BFb0015415"},{"key":"71_CR6","doi-asserted-by":"crossref","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.","DOI":"10.1007\/3-540-57899-4_54"},{"key":"71_CR7","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":"71_CR8","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1137\/S0097539791200375","volume":"23","author":"J. S. Deogun","year":"1994","unstructured":"Deogun, J. S. and G. Steiner, Polynomial algorithms for hamiltonian cycle in cocomparability graphs, SIAM J. Comput. 23 (1994), pp. 520\u2013552.","journal-title":"SIAM J. Comput"},{"key":"71_CR9","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R. and D. S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, 1979."},{"key":"71_CR10","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":"71_CR11","first-page":"325","volume":"21","author":"M. Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel. M., L. Lov\u00e1sz and A. Schrijver, Polynomial algorithms for perfect graphs, Annals of Discrete Mathematics 21 (1984), pp. 325\u2013356.","journal-title":"Annals of Discrete Mathematics"},{"key":"71_CR12","unstructured":"Hastad, J., Clique is hard to approximate within n 1\u2212\u025b , to appear in the Proceedings of FOCS'96."},{"key":"71_CR13","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D. S. Johnson","year":"1985","unstructured":"Johnson, D. S., The NP-completeness column: An ongoing guide, J. Algorithms 6 (1985), pp. 434\u2013451.","journal-title":"J. Algorithms"},{"key":"71_CR14","doi-asserted-by":"crossref","unstructured":"Kloks, T., Treewidth-Computations and Approximations, Springer-Verlag, LNCS 842, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"71_CR15","unstructured":"Kloks, T., D. Kratsch and H. M\u00fcller, A generalization of AT-free graphs and some algorithmic results, Manuscript 1996."},{"key":"71_CR16","series-title":"Memorandum No. 1347","volume-title":"Asteroidal sets in graphs","author":"T. Kloks","year":"1996","unstructured":"Kloks, T., D. Kratsch and H. M\u00fcller, Asteroidal sets in graphs, Memorandum No. 1347, Faculty of Applied Mathematics, University of Twente, Enschede, The Netherlands, 1996."},{"key":"71_CR17","doi-asserted-by":"crossref","unstructured":"Kloks, T., D. Kratsch and J. Spinrad, On treewidth and minimum fill-in of asteroidal triple-free graphs, to appear in Theoretical Computer Science 175 (1997).","DOI":"10.1016\/S0304-3975(96)00206-X"},{"key":"71_CR18","doi-asserted-by":"crossref","unstructured":"Kloks, T., H. M\u00fcller and C. K. Wong, Vertex ranking of asteroidal triple-free graphs, Proceedings of ISAAC'96, Springer-Verlag, LNCS 1178, 1996, pp. 174\u2013182.","DOI":"10.1007\/BFb0009493"},{"key":"71_CR19","volume-title":"Forschungsergebnisse Math\/Inf\/96\/25","author":"D. Kratsch","year":"1996","unstructured":"Kratsch, D., Domination and total domination on asteroidal triple-free graphs, Forschungsergebnisse Math\/Inf\/96\/25, FSU Jena, Germany, 1996."},{"key":"71_CR20","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. Fund. Math. 51 (1962), pp. 45\u201364.","journal-title":"Fund. Math."},{"key":"71_CR21","unstructured":"Lin, I. J., T. A. McKee and D. B. West, Leafage of chordal graphs, Manuscript 1994."},{"key":"71_CR22","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0012-365X(97)89267-9","volume":"162","author":"F. Maffray","year":"1996","unstructured":"Maffray, F. and M. Preissman, On the NP-completeness of the k-colorability problem for trianglefree graphs, Discrete Mathematics 162 (1996), pp. 313\u2013317.","journal-title":"Discrete Mathematics"},{"key":"71_CR23","doi-asserted-by":"publisher","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":"71_CR24","unstructured":"McConnell, R. M. and J. P. Spinrad, Modular decomposition and transitive orientation. Manuscript 1995."},{"key":"71_CR25","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis. M., Computing the minimum fill-in is NP-complete, SIAM J. Alg. Disc. Meth. 2 (1981), pp. 77\u201379.","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63165-8_229.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:16:33Z","timestamp":1605629793000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63165-8_229"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540631651","9783540691945"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-63165-8_229","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}