{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:44:19Z","timestamp":1767339859800},"reference-count":23,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2003,10,1]],"date-time":"2003-10-01T00:00:00Z","timestamp":1064966400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3613,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,10]]},"DOI":"10.1016\/s0166-218x(03)00394-9","type":"journal-article","created":{"date-parts":[[2003,10,24]],"date-time":"2003-10-24T21:50:18Z","timestamp":1067032218000},"page":"109-119","source":"Crossref","is-referenced-by-count":12,"title":["P5-free augmenting graphs and the maximum stable set problem"],"prefix":"10.1016","volume":"132","author":[{"given":"Michael U.","family":"Gerber","sequence":"first","affiliation":[]},{"given":"Alain","family":"Hertz","sequence":"additional","affiliation":[]},{"given":"David","family":"Schindl","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(03)00394-9_BIB1","unstructured":"V.E. Alekseev, On the number of maximal independent sets in graphs from hereditary classes, Combinatorial-algebraic Methods in Applied Mathematics, Gorkiy University Press, Gorkiy, 1991, pp. 5\u20138 (in Russian)."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB2","unstructured":"V.E. Alekseev, A polynomial algorithm for finding largest independent sets in fork-free graphs, Diskretn. Anal. Issled. Oper. Ser. 1(6) (1999) 3\u201319 (in Russian)."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB3","doi-asserted-by":"crossref","unstructured":"V.E. Alekseev, V.V. Lozin, Augmenting graphs for independent sets, Discrete Appl. Math., to appear.","DOI":"10.1016\/j.dam.2003.09.003"},{"key":"10.1016\/S0166-218X(03)00394-9_BIB4","unstructured":"C. Arbib, R. Mosca, On (P5, diamond)-free graphs, Research Report (1999), Department of Pure and Applied Mathematics, University of Aquila."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB5","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/S0166-218X(99)00072-4","article-title":"On the stability number of claw-free P5-free and more general graphs","volume":"95","author":"Brandst\u00e4dt","year":"1999","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB6","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0166-218X(00)00239-0","article-title":"A note on \u03b1-redundant vertices in graphs","volume":"108","author":"Brandst\u00e4dt","year":"2001","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB7","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1137\/0214065","article-title":"A linear recognition algorithm for cographs","volume":"14","author":"Corneil","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB8","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some simplified NP-complete graph problems","volume":"1","author":"Garey","year":"1976","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB9","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0166-218X(01)00321-3","article-title":"On the stable set problem in special P5-free graphs","volume":"125","author":"Gerber","year":"2003","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB10","doi-asserted-by":"crossref","unstructured":"M.U. Gerber, A. Hertz, V.V. Lozin, Stable sets in two subclasses of banner-free graphs, Discrete Appl. Math., this issue.","DOI":"10.1016\/S0166-218X(03)00395-0"},{"key":"10.1016\/S0166-218X(03)00394-9_BIB11","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0166-218X(97)00093-0","article-title":"Weighted parameters in (P5,P5\u0304)-free graphs","volume":"80","author":"Giakoumakis","year":"1997","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB12","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0012-365X(78)90178-4","article-title":"Trivially perfect graphs","volume":"24","author":"Golumbic","year":"1978","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB13","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/S0377-2217(99)00460-9","article-title":"Stability in P5 and banner-free graphs","volume":"125","author":"Lozin","year":"2000","journal-title":"European J. Oper. Res."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB14","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","article-title":"Modular decomposition and transitive orientation","volume":"201","author":"McConnell","year":"1999","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB15","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","article-title":"On maximal independent sets of vertices in claw-free graphs","volume":"28","author":"Minty","year":"1980","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0166-218X(03)00394-9_BIB16","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0020-0190(96)00197-4","article-title":"Polynomial algorithms for the maximum independent set problem on particular classes of P5-free graphs","volume":"61","author":"Mosca","year":"1997","journal-title":"Inform. Proc. Lett."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB17","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0166-218X(99)00046-3","article-title":"Stable sets in certain P6-free graphs","volume":"92","author":"Mosca","year":"1999","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB18","unstructured":"R. Mosca, Some results on maximum stable sets in certain P5-free graphs, unpublished manuscript, Universita degli Studi di L'Aqila, Italy (1999)."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB19","first-page":"307","article-title":"A note on stable sets and coloring of graphs","volume":"15","author":"Poljak","year":"1974","journal-title":"Comment. Math. Univ. Carolinae"},{"key":"10.1016\/S0166-218X(03)00394-9_BIB20","doi-asserted-by":"crossref","unstructured":"N. Sbihi, Algorithme de recherche d'un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile, Discrete Math. 29 (1980) 53\u201376 (in French).","DOI":"10.1016\/0012-365X(90)90287-R"},{"key":"10.1016\/S0166-218X(03)00394-9_BIB21","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","article-title":"A new algorithm for generating all the maximal independent sets","volume":"6","author":"Tsukiyama","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB22","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0166-218X(96)00094-7","article-title":"Quasi-threshold graphs","volume":"69","author":"Yan","year":"1996","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(03)00394-9_BIB23","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1137\/0603036","article-title":"The complexity of the partial order dimension problem","volume":"3","author":"Yannakakis","year":"1982","journal-title":"SIAM J. Algebraic Discrete Methods"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X03003949?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X03003949?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,18]],"date-time":"2019-02-18T23:26:21Z","timestamp":1550532381000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X03003949"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,10]]},"references-count":23,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2003,10]]}},"alternative-id":["S0166218X03003949"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(03)00394-9","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,10]]}}}