{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:20:43Z","timestamp":1740097243758,"version":"3.37.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"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-319-42634-1_31","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:50:21Z","timestamp":1468929021000},"page":"385-392","source":"Crossref","is-referenced-by-count":2,"title":["Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs"],"prefix":"10.1007","author":[{"given":"T.","family":"Karthick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Maffray","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"31_CR1","unstructured":"Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. In: Combinatorial-Algebraic Methods in Applied Mathematics, pp. 3\u201313. Gorkiy University Press, Gorky (1982). (in Russian)"},{"key":"31_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1007\/978-3-540-85238-4_7","volume-title":"Mathematical Foundations of Computer Science 2008","author":"VE Alekseev","year":"2008","unstructured":"Alekseev, V.E., Lozin, V.V., Malyshev, D., Milani\u010d, M.: The maximum independent set problem in planar graphs. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 96\u2013107. Springer, Heidelberg (2008)"},{"key":"31_CR3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity - A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"31_CR4","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":"31_CR5","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- and Diamond-free graphs and algorithmic consequences. Discrete Appl. Math. 160, 471\u2013478 (2012)","journal-title":"Discrete Appl. Math."},{"key":"31_CR6","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/j.tcs.2007.09.031","volume":"389","author":"A Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt, A., Ho\u00e1ng, C.T.: On clique separators, nearly chordal graphs, and the maximum weight stable set problem. Theor. Comput. Sci. 389, 295\u2013306 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"31_CR7","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.dam.2015.07.032","volume":"201","author":"A Brandst\u00e4dt","year":"2016","unstructured":"Brandst\u00e4dt, A., Karthick, T.: Weighted efficient domination in two subclasses of $$P_6$$ -free graphs. Discrete Appl. Math. 201, 38\u201346 (2016)","journal-title":"Discrete Appl. Math."},{"key":"31_CR8","series-title":"SIAM Monographs on Discrete Mathematics","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 Mathematics, vol. 3. SIAM, Philadelphia (1999)"},{"issue":"1","key":"31_CR9","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1137\/090750822","volume":"24","author":"A Brandst\u00e4dt","year":"2010","unstructured":"Brandst\u00e4dt, A., Lozin, V.V., Mosca, R.: Independent sets of maximum weight in apple-free graphs. SIAM J. Discrete Math. 24(1), 239\u2013254 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"31_CR10","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":"31_CR11","doi-asserted-by":"crossref","first-page":"1766","DOI":"10.1016\/j.disc.2015.01.041","volume":"338","author":"C Brause","year":"2015","unstructured":"Brause, C., Le, N.C., Schiermeyer, I.: The maximum independent det problem in subclasses of subcubic graphs. Discrete Math. 338, 1766\u20131778 (2015)","journal-title":"Discrete Math."},{"key":"31_CR12","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":"31_CR13","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":"31_CR14","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0166-218X(85)90027-7","volume":"12","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G.: The complexity of generalized clique packing. Discrete Appl. Math. 12, 233\u2013240 (1985)","journal-title":"Discrete Appl. Math."},{"key":"31_CR15","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition for cographs. SIAM J. Comput. 14, 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"key":"31_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"31_CR17","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0012-365X(89)90268-9","volume":"73","author":"M Farber","year":"1989","unstructured":"Farber, M.: On diameters and radii of bridged graphs. Discrete Math. 73, 249\u2013260 (1989)","journal-title":"Discrete Math."},{"key":"31_CR18","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0166-218X(03)00395-0","volume":"132","author":"MU Gerber","year":"2004","unstructured":"Gerber, M.U., Hertz, A., Lozin, V.V.: Stable sets in two subclasses of banner-free graphs. Discrete Appl. Math. 132, 121\u2013136 (2004)","journal-title":"Discrete Appl. Math."},{"key":"31_CR19","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"31_CR20","unstructured":"Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Proceedings of the Fifth BCC, Congressus Numerantium, XV, pp. 211\u2013226 (1976)"},{"key":"31_CR21","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, New York (1972)"},{"key":"31_CR22","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":"31_CR23","doi-asserted-by":"crossref","unstructured":"Karthick, T., Maffray, F.: Maximum weight independent sets inclasses related to claw-free graphs. Discrete Appl. Math. (2015). http:\/\/dx.doi.org\/10.1016\/j.dam.2015.02.012","DOI":"10.1016\/j.dam.2015.02.012"},{"key":"31_CR24","doi-asserted-by":"crossref","first-page":"1674","DOI":"10.1016\/j.disc.2014.07.002","volume":"338","author":"NC Le","year":"2015","unstructured":"Le, N.C., Brause, C., Schiermeyer, I.: New sufficient conditions for $$\\alpha $$ -redundant vertices. Discrete Math. 338, 1674\u20131680 (2015)","journal-title":"Discrete Math."},{"key":"31_CR25","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 Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 570\u2013581 (2014)","DOI":"10.1137\/1.9781611973402.43"},{"key":"31_CR26","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":"31_CR27","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s00373-012-1263-y","volume":"30","author":"VV Lozin","year":"2014","unstructured":"Lozin, V.V., Milani\u010d, M., Purcell, C.: Graphs without large apples and the maximum weight independent set problem. Graphs Comb. 30, 395\u2013410 (2014)","journal-title":"Graphs Comb."},{"key":"31_CR28","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.jda.2014.08.005","volume":"31","author":"VV Lozin","year":"2015","unstructured":"Lozin, V.V., Monnot, J., Ries, B.: On the maximum independent set problem in subclasses of subcubic graphs. J. Discrete Algorithms 31, 104\u2013112 (2015)","journal-title":"J. Discrete Algorithms"},{"key":"31_CR29","doi-asserted-by":"crossref","unstructured":"Maffray, F., Pastor, L.: The maximum weight stable set problem in ( $$P_6$$ , bull)-free graphs (2016). arXiv:1602.06817v1","DOI":"10.1007\/978-3-662-53536-3_8"},{"key":"31_CR30","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1134\/S199047891304008X","volume":"7","author":"DS Malyshev","year":"2013","unstructured":"Malyshev, D.S.: Classes of subcubic planar graphs for which the indepedent set problem is polynomial-time solvable. J. Appl. Ind. Math. 7, 537\u2013548 (2013)","journal-title":"J. Appl. Ind. Math."},{"key":"31_CR31","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GM Minty","year":"1980","unstructured":"Minty, G.M.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theor. Ser. B 28, 284\u2013304 (1980)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"31_CR32","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Commun. Math. Univ. Carolinae 15, 307\u2013309 (1974)","journal-title":"Commun. Math. Univ. Carolinae"},{"key":"31_CR33","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":"31_CR34","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\/s00453-015-0083-x"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T07:04:06Z","timestamp":1568185446000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}