{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T09:42:45Z","timestamp":1791279765781,"version":"4.1.0"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>\n                    An asteroidal triple (AT) is a set of three vertices such that there is a path between any pair of them avoiding the closed neighborhood of the third. A graph is called AT-free if it does not have an AT. We show that there is an O(n\n                    <jats:sup>4<\/jats:sup>\n                    ) time algorithm to compute the maximum weight of an independent set for AT-free graphs. Furthermore, we obtain O(n\n                    <jats:sup>4<\/jats:sup>\n                    ) time algorithms to solve the INDEPENDENT DOMINATING SET and the INDEPENDENT PERFECT DOMINATING SET problems on AT-free graphs. We also show how to adapt these algorithms such that they solve the corresponding problem for graphs with bounded asteroidal number in polynomial time. Finally, we observe that the problems CLIQUE and PARTITION INTO CLIQUES remain NP-complete when restricted to AT-free graphs.\n                  <\/jats:p>","DOI":"10.1137\/s0895480197326346","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"276-287","source":"Crossref","is-referenced-by-count":62,"title":["Independent Sets in Asteroidal Triple-Free Graphs"],"prefix":"10.1137","volume":"12","author":[{"given":"Hajo","family":"Broersma","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ton","family":"Kloks","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"HariBalakrishnan, AnandRajaraman, C.Pandu Rangan, Connected domination and Steiner set on asteroidal triple\u2010free graphs, Lecture Notes in Comput. Sci., Vol. 709, Springer, Berlin, 1993, 131\u201314194k:05177","DOI":"10.1007\/3-540-57155-8_242"},{"key":"R3","unstructured":"A. Brandst\u00e4dt,\n                      Special graph classes \u2013 A survey\n                      , Schriftenreihe des Fachbereichs Mathematik, SM\u2010DU\u2010199, Universit\u00e4t Duisburg Gesamthochschule, Duisburg, Germany, 1991."},{"key":"R4","unstructured":"H. Breu and D. G. Kirkpatrick,\n                      Algorithms for Domination and Steiner Tree Problems in Cocomparability Graphs\n                      , University of British Columbia, Vancouver, manuscript 1993."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Maw\u2010ShangChang, Weighted domination on cocomparability graphs, Lecture Notes in Comput. Sci., Vol. 1004, Springer, Berlin, 1995, 122\u201313197b:68083","DOI":"10.1007\/BFb0015415"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193250125"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"D. G. Corneil, S. Olariu, and L. Stewart,\n                      A linear time algorithm to compute dominating pairs in asteroidal triple\u2010free graphs\n                      , in Proceedings of ICALP\u201995, Lecture Notes in Computer Science 944, Springer\u2010Verlag, New York, 1995, pp. 292\u2013302.","DOI":"10.1007\/3-540-60084-1_82"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791200375"},{"key":"R9","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP\u2010Completeness\n                      , Freeman, San Francisco, 1979."},{"key":"R10","volume-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic Martin","year":"1980"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"M.Gr\u00f6tschel, L.Lov\u00e1sz, A.Schrijver, Polynomial algorithms for perfect graphs, North\u2010Holland Math. Stud., Vol. 88, North\u2010Holland, Amsterdam, 1984, 325\u201335686g:05073","DOI":"10.1016\/S0304-0208(08)72943-8"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"J. Hastad,\n                      Clique is hard to approximate withinn1-\u03b5\n                      , in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, Burlington, VT, 1996, pp. 627\u2013636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90012-4"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"T. Kloks,\n                      Treewidth \u2013 Computations and Approximations\n                      , Lecture Notes in Computer Science 842, Springer\u2010Verlag, New York, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"H. J. Broersma, T. Kloks, D. Kratsch, and H. M\u00fcller,\n                      A generalization of AT\u2010free graphs and a generic algorithm for solving triangulation problems\n                      , in Proceedings of WG\u201998, Lecture Notes in Computer Science 1517, Springer\u2010Verlag, New York, 1998, pp. 88\u201389.","DOI":"10.1007\/10692760_8"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"TonKloks, DieterKratsch, HaikoM\u00fcller, Asteroidal sets in graphs, Lecture Notes in Comput. Sci., Vol. 1335, Springer, Berlin, 1997, 229\u201324199d:68112","DOI":"10.1007\/BFb0024501"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00206-X"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00162-8"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"DieterKratsch, Domination and total domination on asteroidal triple\u2010free graphs, Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997), Vol. 99, 2000, 111\u20131231743827","DOI":"10.1016\/S0166-218X(99)00128-6"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.4064\/fm-51-1-45-64"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1061"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)89267-9"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00095-9"},{"key":"R24","unstructured":"RossMcConnell, JeremySpinrad, Linear\u2010time transitive orientation, ACM, New York, 1997, 19\u2013251447646"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02941616"},{"key":"R26","unstructured":"R. Uehara,\n                      NP\u2010Complete Problems on a 3\u2010Connected Cubic Planar Graph and Their Applications\n                      , Technical report TWCU\u2010M\u20100004, Tokyo Woman\u2019s Christian University, 1996."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020311"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480197326346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:50:11Z","timestamp":1787316611000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480197326346"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1137\/S0895480197326346"],"URL":"https:\/\/doi.org\/10.1137\/s0895480197326346","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}