{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:33:43Z","timestamp":1742920423000,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662535356"},{"type":"electronic","value":"9783662535363"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53536-3_8","type":"book-chapter","created":{"date-parts":[[2016,9,27]],"date-time":"2016-09-27T16:39:25Z","timestamp":1474994365000},"page":"85-96","source":"Crossref","is-referenced-by-count":5,"title":["The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs"],"prefix":"10.1007","author":[{"given":"Fr\u00e9d\u00e9ric","family":"Maffray","sequence":"first","affiliation":[]},{"given":"Lucas","family":"Pastor","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,28]]},"reference":[{"key":"8_CR1","first-page":"3","volume":"132","author":"VE Alekseev","year":"1983","unstructured":"Alekseev, V.E.: On the local restrictions effect on the complexity of finding the graph independence number. Comb. Algebraic Methods Appl. Math. 132, 3\u201313 (1983). Gorkiy Universty Press (in Russian)","journal-title":"Comb. Algebraic Methods Appl. Math."},{"issue":"6","key":"8_CR2","first-page":"3","volume":"1","author":"VE Alekseev","year":"1999","unstructured":"Alekseev, V.E.: A polynomial algorithm for finding maximum independent sets in fork-free graphs. Discrete Anal. Oper. Res. Ser. 1(6), 3\u201319 (1999). (in Russian)","journal-title":"Discrete Anal. Oper. Res. Ser."},{"key":"8_CR3","first-page":"123","volume":"9","author":"C Berge","year":"1960","unstructured":"Berge, C.: Les probl\u00e8mes de coloration en th\u00e9orie des graphes. Publ. Inst. Stat. Univ. Paris 9, 123\u2013160 (1960)","journal-title":"Publ. Inst. Stat. Univ. Paris"},{"key":"8_CR4","first-page":"114","volume":"10","author":"C Berge","year":"1961","unstructured":"Berge, C.: F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw.\u00a0derenungerade Kreise starr sind (Zusammenfassung). Wiss. Z. MartinLuther Univ. Math. Natur. Reihe (Halle-Wittenberg) 10, 114\u2013115 (1961)","journal-title":"Wiss. Z. MartinLuther Univ. Math. Natur. Reihe (Halle-Wittenberg)"},{"key":"8_CR5","volume-title":"Graphs","author":"C Berge","year":"1985","unstructured":"Berge, C.: Graphs. North-Holland, Amsterdam (1985)"},{"key":"8_CR6","doi-asserted-by":"crossref","first-page":"173","DOI":"10.46298\/dmtcs.372","volume":"8","author":"A Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Klembt, T., Mahfud, S.: $$P_6$$ - and triangle-free graphs revisited: Structure and bounded clique-width. Discrete Math. Theor. Comput. Sci. 8, 173\u2013188 (2006)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"8_CR7","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.1007\/s00373-014-1461-x","volume":"31","author":"A Brandst\u00e4dt","year":"2015","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Maximum weight independent sets in odd-hole-free graphs without dart or without bull. Graphs Comb. 31, 1249\u20131262 (2015)","journal-title":"Graphs Comb."},{"key":"8_CR8","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/j.jctb.2011.07.003","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky, M.: The structure of bull-free graphs I: three-edge paths with centers and anticenters. J. Comb. Theor. B 102, 233\u2013251 (2012)","journal-title":"J. Comb. Theor. B"},{"key":"8_CR9","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/j.jctb.2011.07.002","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky, M.: The structure of bull-free graphs II and III: a summary. J. Comb. Theor. B 102, 252\u2013282 (2012)","journal-title":"J. Comb. Theor. B"},{"key":"8_CR10","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":"8_CR11","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46, 218\u2013270 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR12","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique width. Theor. Comput. Syst. 33, 125\u2013150 (2000)","journal-title":"Theor. Comput. Syst."},{"key":"8_CR13","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/S0895480198339237","volume":"18","author":"CMH Figueiredo de","year":"2004","unstructured":"de Figueiredo, C.M.H., Maffray, F.: Optimizing bull-free perfect graphs. SIAM J. Discrete Math. 18, 226\u2013240 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"8_CR14","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":"8_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/3-540-46784-X_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"MC Golumbic","year":"1999","unstructured":"Golumbic, M.C., Rotics, U.: On the clique\u2014width of perfect graph classes. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol. 1665, pp. 135\u2013147. Springer, Heidelberg (1999). doi: 10.1007\/3-540-46784-X_14"},{"key":"8_CR17","doi-asserted-by":"crossref","first-page":"1412","DOI":"10.1016\/j.disc.2015.12.008","volume":"339","author":"T Karthick","year":"2016","unstructured":"Karthick, T.: Weighted independent sets in a subclass of $$P_6$$ -free graphs. Discrete Math. 339, 1412\u20131418 (2016)","journal-title":"Discrete Math."},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.dam.2015.10.015","volume":"209","author":"T Karthick","year":"2016","unstructured":"Karthick, T., Maffray, F.: Weighted independent sets in classes of $$P_6$$ -free graphs. Discrete Appl. Math. 209, 217\u2013226 (2016). doi: 10.1016\/j.dam.2015.10.015","journal-title":"Discrete Appl. Math."},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Pilipczuk, M., van\u00a0Leeuwen, E.J.: Independence andefficient domination on $$P_6$$ -free graphs. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1784\u20131803. ACM, New York (2016)","DOI":"10.1137\/1.9781611974331.ch124"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in $$ P_5$$ -free graphs in polynomial time. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 570\u2013581. ACM, NewYork (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"8_CR21","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/j.jda.2008.04.001","volume":"6","author":"VV Lozin","year":"2008","unstructured":"Lozin, V.V., Milani\u010d, M.: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discrete Algorithms 6, 595\u2013604 (2008)","journal-title":"J. Discrete Algorithms"},{"key":"8_CR22","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.dam.2004.07.006","volume":"146","author":"VV Lozin","year":"2005","unstructured":"Lozin, V.V., Mosca, R.: Independent sets in extensions of $$2K_2$$ -free graphs. Discrete Appl. Math. 146, 74\u201380 (2005)","journal-title":"Discrete Appl. Math."},{"key":"8_CR23","unstructured":"Maffray, F., Pastor, L.: 4-coloring $$(P_6,\\text{bull})$$ -free graphs. arXiv:1511.08911 . To appear in Discrete Applied Mathematics"},{"key":"8_CR24","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0166-218X(99)00046-3","volume":"92","author":"R Mosca","year":"1999","unstructured":"Mosca, R.: Stable sets in certain $$P_6$$ -free graphs. Discrete Appl. Math. 92, 177\u2013191 (1999)","journal-title":"Discrete Appl. Math."},{"key":"8_CR25","first-page":"125","volume":"11","author":"R Mosca","year":"2009","unstructured":"Mosca, R.: Independent sets in ( $$P_6$$ , diamond)-free graphs. Discrete Math. Theor. Comput. Sci. 11, 125\u2013140 (2009)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"8_CR26","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.ipl.2012.10.004","volume":"113","author":"R Mosca","year":"2013","unstructured":"Mosca, R.: Maximum weight independent sets in ( $$P_6$$ , co-banner)-free graphs. Inf. Process. Lett. 113, 89\u201393 (2013)","journal-title":"Inf. Process. Lett."},{"key":"8_CR27","doi-asserted-by":"crossref","first-page":"1281","DOI":"10.1137\/110825637","volume":"26","author":"I Penev","year":"2012","unstructured":"Penev, I.: Coloring bull-free perfect graphs. SIAM J. Discrete Math. 26, 1281\u20131309 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"8_CR28","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF01929485","volume":"11","author":"B Reed","year":"1995","unstructured":"Reed, B., Sbihi, N.: Recognizing bull-free perfect graphs. Graphs Comb. 11, 171\u2013178 (1995)","journal-title":"Graphs Comb."},{"key":"8_CR29","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S., Trotignon, N., Vu\u0161kovi\u0107, K.: A polynomial Turing-kernel for weighted independent set in bull-free graphs. Algorithmica (2015, in press)","DOI":"10.1007\/978-3-319-12340-0_34"}],"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\/978-3-662-53536-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,9]],"date-time":"2022-07-09T08:09:34Z","timestamp":1657354174000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53536-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662535356","9783662535363"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53536-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}