{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T19:34:56Z","timestamp":1773257696891,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2014,8,10]],"date-time":"2014-08-10T00:00:00Z","timestamp":1407628800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00373-014-1461-x","type":"journal-article","created":{"date-parts":[[2014,8,9]],"date-time":"2014-08-09T07:17:36Z","timestamp":1407568656000},"page":"1249-1262","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Maximum Weight Independent Sets in Odd-Hole-Free Graphs Without Dart or Without Bull"],"prefix":"10.1007","volume":"31","author":[{"given":"Andreas","family":"Brandst\u00e4dt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raffaele","family":"Mosca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,8,10]]},"reference":[{"key":"1461_CR1","doi-asserted-by":"crossref","first-page":"2364","DOI":"10.1016\/j.dam.2012.06.015","volume":"160","author":"M Basavaraju","year":"2012","unstructured":"Basavaraju, M., Chandran, L.S., Karthick, T.: Maximum weight independent sets in hole- and dart-free graphs. Discrete Appl. Math. 160, 2364\u20132369 (2012)","journal-title":"Discrete Appl. Math."},{"key":"1461_CR2","first-page":"164","volume":"7","author":"A Berry","year":"2000","unstructured":"Berry, A., Bordat, J.-P., Heggernes, P.: Recognizing weakly triangulated graphs by edge separability. Nord. J. Comput. 7, 164\u2013177 (2000)","journal-title":"Nord. J. Comput."},{"key":"1461_CR3","unstructured":"Berry, A., Brandst\u00e4dt, A., Giakoumakis, V., Maffray, F.: Efficiently recognizing, decomposing and triangulating hole- and diamond-free graphs, manuscript 2012; accepted for Discrete Appl. Math. (2012)"},{"key":"1461_CR4","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0166-218X(03)00266-X","volume":"138","author":"A Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A.: ( $$P_5$$ P 5 , diamond)-free graphs revisited: structure and linear time optimization. Discrete Appl. Math. 138, 13\u201327 (2004)","journal-title":"Discrete Appl. Math."},{"key":"1461_CR5","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.ipl.2011.09.015","volume":"112","author":"A Brandst\u00e4dt","year":"2012","unstructured":"Brandst\u00e4dt, A., Giakoumakis, V.: Maximum weight independent sets in hole- and co-chair-free graphs. Inf. Process. Lett. 112, 67\u201371 (2012)","journal-title":"Inf. Process. Lett."},{"key":"1461_CR6","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1016\/j.dam.2011.10.031","volume":"160","author":"A Brandst\u00e4dt","year":"2012","unstructured":"Brandst\u00e4dt, A., Giakoumakis, V., Maffray, F.: Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences. Discrete Appl. Math. 160, 471\u2013478 (2012)","journal-title":"Discrete Appl. Math."},{"key":"1461_CR7","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0166-218X(02)00415-8","volume":"131","author":"A Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Ho\u00e0ng, C.T., Le, V.B.: Stability number of bull- and chair-free graphs revisited. Discrete Appl. Math. 131, 39\u201350 (2003)","journal-title":"Discrete Appl. Math."},{"key":"1461_CR8","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/s00453-008-9176-0","volume":"56","author":"A Brandst\u00e4dt","year":"2010","unstructured":"Brandst\u00e4dt, A., Klembt, T., Lozin, V.V., Mosca, R.: On independent vertex sets in subclasses of apple-free graphs. Algorithmica 56, 383\u2013393 (2010)","journal-title":"Algorithmica"},{"key":"1461_CR9","series-title":"SIAM Monographs on Discrete Math. Appl., Vol. 3","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Math. Appl., Vol. 3. SIAM, Philadelphia (1999)"},{"key":"1461_CR10","doi-asserted-by":"crossref","unstructured":"Chudnovsky, M.: The structure of bull-free graphs II and III\u2014A summary, J. Comb. Theory Ser. B 102, 252\u2013282 (2012)","DOI":"10.1016\/j.jctb.2011.07.002"},{"key":"1461_CR11","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Cornu\u00e9jols, G., Liu, X., Seymour, P., Vuskovi\u010d, K.: Recognizing Berge graphs. Combinatorica 25, 143\u2013186 (2005)","journal-title":"Combinatorica"},{"key":"1461_CR12","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"1461_CR13","doi-asserted-by":"crossref","first-page":"1315","DOI":"10.1137\/S0097539799354771","volume":"31","author":"V Chv\u00e1tal","year":"2002","unstructured":"Chv\u00e1tal, V., Fonlupt, J., Sun, L., Zemirline, A.: Recognizing dart-free perfect graphs. SIAM J. Comput. 31, 1315\u20131338 (2002)","journal-title":"SIAM J. Comput."},{"key":"1461_CR14","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1137\/S089548010444540X","volume":"20","author":"M Conforti","year":"2006","unstructured":"Conforti, M., Cornu\u00e9jols, G., Liu, X., Vu\u0161kovic, K., Zambelli, G.: Odd hole recognition in graphs of bounded clique size. SIAM J. Discrete Math. 20, 42\u201348 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"1461_CR15","doi-asserted-by":"crossref","unstructured":"Cornu\u00e9jols, G., Liu, X., Vu\u0161kovic, K.: A polynomial algorithm for recognizing perfect graphs. In: Procedings 44th annals of IEEE symposium on foundations of computer science FOCS 2003, pp. 20\u201327 (2003)","DOI":"10.1109\/SFCS.2003.1238177"},{"key":"1461_CR16","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01195324","volume":"9","author":"C Simone De","year":"1993","unstructured":"De Simone, C.: On the vertex packing problem. Graphs Comb. 9, 19\u201330 (1993)","journal-title":"Graphs Comb."},{"key":"1461_CR17","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0166-218X(93)90032-J","volume":"9","author":"C Simone De","year":"1993","unstructured":"De Simone, C., Sassano, A.: Stability number of bull- and chair-free graphs. Discrete Appl. Math. 9, 121\u2013129 (1993)","journal-title":"Discrete Appl. Math."},{"key":"1461_CR18","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/BF01202235","volume":"13","author":"CMH Figueiredo De","year":"1997","unstructured":"De Figueiredo, C.M.H., Maffray, F., Porto, O.: On the structure of bull-free perfect graphs. Graphs Comb. 13, 31\u201355 (1997)","journal-title":"Graphs Comb."},{"key":"1461_CR19","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1006\/jctb.1995.1048","volume":"65","author":"EM Eschen","year":"1995","unstructured":"Eschen, E.M., Sritharan, R.: A characterization of some graph classes with no long holes. J. Comb. Theory Ser. B 65, 156\u2013162 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1461_CR20","first-page":"271","volume":"49","author":"GH Fricke","year":"1998","unstructured":"Fricke, G.H., Hedetniemi, S.T., Jacobs, D.P.: Independence and irredundance in $$k$$ k -regular graphs. Ars Comb. 49, 271\u2013279 (1998)","journal-title":"Ars Comb."},{"key":"1461_CR21","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0012-365X(93)90539-6","volume":"121","author":"J-L Fouquet","year":"1993","unstructured":"Fouquet, J.-L.: A decomposition for a class of $$(P_5,{\\overline{P_5}})$$ ( P 5 , P 5 \u00af ) -free graphs. Discrete Math. 121, 75\u201383 (1993)","journal-title":"Discrete Math."},{"key":"1461_CR22","first-page":"325","volume":"21","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. Ann. Discrete Math. 21, 325\u2013356 (1984)","journal-title":"Ann. Discrete Math."},{"key":"1461_CR23","doi-asserted-by":"crossref","unstructured":"Hayward, R.B., Spinrad, J.B., Sritharan, R.: Improved algorithms for weakly chordal graphs, ACM Trans. Algorithms 3 (2007). Article 14","DOI":"10.1145\/1240233.1240237"},{"key":"1461_CR24","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201, 189\u2013241 (1999)","journal-title":"Discrete Math."},{"key":"1461_CR25","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0166-218X(03)00399-8","volume":"132","author":"R Mosca","year":"2004","unstructured":"Mosca, R.: Some results on maximum stable sets in certain $$P_5$$ P 5 -free graphs. Discrete Appl. Math. 132, 175\u2013183 (2004)","journal-title":"Discrete Appl. Math."},{"key":"1461_CR26","unstructured":"Penev, I.: Forbidden substructures in graphs and trigraphs, and related coloring problems, PhD Thesis, Columbia University (2012)"},{"key":"1461_CR27","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0020-0190(91)90184-J","volume":"39","author":"JP Spinrad","year":"1991","unstructured":"Spinrad, J.P.: Finding large holes. Inf. Process. Lett. 39, 227\u2013229 (1991)","journal-title":"Inf. Process. Lett."},{"key":"1461_CR28","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0166-218X(93)E0161-Q","volume":"59","author":"JP Spinrad","year":"1995","unstructured":"Spinrad, J.P., Sritharan, R.: Algorithms for weakly triangulated graphs. Discrete Appl. Math. 59, 181\u2013191 (1995)","journal-title":"Discrete Appl. Math."},{"key":"1461_CR29","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55, 221\u2013232 (1985)","journal-title":"Discrete Math."},{"key":"1461_CR30","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S., Trotignon, N., Vuskovi\u010d, K.: Parameterized algorithm for weighted independent set problem in bull-free graphs, Technical report 2013; available online","DOI":"10.1007\/978-3-319-12340-0_34"},{"key":"1461_CR31","unstructured":"Vuskovi\u010d, K.:Personal communication"},{"key":"1461_CR32","volume-title":"Topics on Perfect Graphs","author":"SH Whitesides","year":"1984","unstructured":"Whitesides, S.H.: A method for solving certain graph recognition and optimization problems, with applications to perfect graphs. In: Berge, C., Chv\u00e1tal, V. (eds.) Topics on Perfect Graphs. North-Holland, Amsterdam (1984)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-014-1461-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-014-1461-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-014-1461-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T18:53:33Z","timestamp":1565722413000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-014-1461-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,10]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["1461"],"URL":"https:\/\/doi.org\/10.1007\/s00373-014-1461-x","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,10]]}}}