{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:14Z","timestamp":1725488594420},"publisher-location":"Berlin, Heidelberg","reference-count":52,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_51","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:32:26Z","timestamp":1186727546000},"page":"445-458","source":"Crossref","is-referenced-by-count":2,"title":["On Robust Algorithms for the Maximum Weight Stable Set Problem"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Brandst\u00e4dt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"issue":"4","key":"51_CR1","first-page":"3","volume":"6","author":"V.E. Alekseev","year":"1999","unstructured":"V.E. Alekseev, A polynomial algorithm for finding maximum independent sets in fork-free graphs, Discr. Analysis and Oper. Research Vol. 6 No. 4 (1999) 3\u201319","journal-title":"Discr. Analysis and Oper. Research"},{"key":"51_CR2","unstructured":"C. Arbib, R. Mosca, On the stable set problem in (P\n                           5, diamond)-free graphs, Manuscript 1995"},{"key":"51_CR3","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0166-218X(99)00062-1","volume":"95","author":"L. Babel","year":"1999","unstructured":"L. Babel, S. Olariu, On the p-connectedness of graphs: A survey, Discrete Applied Math. 95 (1999) 11\u201333","journal-title":"Discrete Applied Math."},{"key":"51_CR4","unstructured":"A. Brandst\u00e4dt, (P\n                           5,diamond)-Free Graphs Revisited: Structure and Linear Time Optimization, Manuscript 2000"},{"key":"51_CR5","unstructured":"A. Brandst\u00e4dt, F.F. Dragan, On the clique width of graph classes defined by three forbidden P\n                           4 extensions, Manuscript 2001"},{"key":"51_CR6","unstructured":"A. Brandst\u00e4dt, V. Giakoumakis, J.-M. Vanherpe, On Prime (P\n                           5,Claw)-Free, (P\n                           5,Bull)-Free, and (Bull,Claw)-Free Graphs and the Maximum Stable Set Problem, Manuscript 2001"},{"key":"51_CR7","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0166-218X(99)00072-4","volume":"95","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"A. Brandst\u00e4dt, P.L. Hammer, On the stability number of claw-free P\n                           5-free and more general graphs, Discrete Applied Math. 95 (1999) 163\u2013167","journal-title":"Discrete Applied Math."},{"key":"51_CR8","unstructured":"A. Brandst\u00e4dt, C.T. Ho\u00e0ng, V.B. Le, Stability number of bull-and chair-free graphs revisited, Manuscript 2001"},{"key":"51_CR9","volume-title":"RUTCOR Research Report","author":"A. Brandst\u00e4dt","year":"2001","unstructured":"A. Brandst\u00e4dt, C.T. Ho\u00e0ng, I. Zverovich, Extension of claw-free graphs and (K\n                           1 \u222a P\n                           4)-free graphs with substitutions, RUTCOR Research Report, Rutgers University, New Brunswick NJ, 28-2001 (2001)"},{"key":"51_CR10","unstructured":"A. Brandst\u00e4dt, C.T. Ho\u00e0ng, I. Zverovich, All extensions of a four-vertex graph in a prime graph, Manuscript in preparation, 2001"},{"key":"51_CR11","unstructured":"A. Brandst\u00e4dt, D. Kratsch, On (P\n                           5,Gem)-Free Graphs and Related Graph Classes: Structure and Algorithmic Applications, Manuscript 2001"},{"key":"51_CR12","unstructured":"A. Brandst\u00e4dt, H.-O. Le, J.-M. Vanherpe, Structure and Stability Number of (Chair,Co-P,Gem)-Free Graphs Revisited, Manuscript 2001"},{"key":"51_CR13","volume-title":"SIAM Monographs on Discrete Math. Appl.","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"A. Brandst\u00e4dt, V.B. Le, J. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Math. Appl., Vol. 3, SIAM, Philadelphia (1999)"},{"key":"51_CR14","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/S0166-218X(00)00239-0","volume":"108","author":"A. Brandst\u00e4dt","year":"2001","unstructured":"A. Brandst\u00e4dt, V.V. Lozin, A note on \u03b1-redundant vertices in graphs, Discrete Applied Math. 108 (2001) 301\u2013308","journal-title":"Discrete Applied Math."},{"key":"51_CR15","unstructured":"A. Brandst\u00e4dt, R. Mosca, On the Structure and Stability Number of P\n                           5-and Co-Chair-Free Graphs, Manuscript 2001"},{"key":"51_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(85)90027-7","volume":"12","author":"D.G. Corneil","year":"1985","unstructured":"D.G. Corneil The complexity of generalized clique packing, Discrete Applied Math. 12 (1985) 233\u2013239","journal-title":"Discrete Applied Math."},{"key":"51_CR17","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D.G. Corneil","year":"1981","unstructured":"D.G. Corneil, H. Lerchs, L. Stewart-Burlingham, Complement reducible graphs, Discrete Applied Math. 3 (1981) 163\u2013174","journal-title":"Discrete Applied Math."},{"key":"51_CR18","first-page":"249","volume":"43","author":"D.G. Corneil","year":"1984","unstructured":"D.G. Corneil, Y. Perl, L.K. Stewart, Cographs: recognition, applications, and algorithms, Congressus Numer. 43 (1984) 249\u2013258","journal-title":"Congressus Numer."},{"key":"51_CR19","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D.G. Corneil","year":"1985","unstructured":"D.G. Corneil, Y. Perl, L.K. Stewart, A linear recognition algorithm for cographs, SIAM J. Computing 14 (1985) 926\u2013934","journal-title":"SIAM J. Computing"},{"key":"51_CR20","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B. Courcelle","year":"1993","unstructured":"B. Courcelle, J. Engelfriet, G. Rozenberg, Handle-rewriting hypergraph grammars, J. Comput. Syst. Sciences, 46 (1993) 218\u2013270","journal-title":"J. Comput. Syst. Sciences"},{"key":"51_CR21","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Conf. Proc. WG\u201998","author":"B. Courcelle","year":"1998","unstructured":"B. Courcelle, J.A. Makowsky, U. Rotics, Linear time solvable optimization problems on graphs of bounded clique width, extended abstract in: Conf. Proc. WG\u201998, LNCS 1517 (1998) 1\u201316"},{"key":"51_CR22","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"B. Courcelle, S. Olariu, Upper bounds to the clique width of graphs, Discrete Appl. Math. 101 (2000) 77\u2013114","journal-title":"Discrete Appl. Math."},{"key":"51_CR23","series-title":"Lect Notes Comput Sci","volume-title":"LIRMM, University Montpellier","author":"A. Cournier","year":"1995","unstructured":"A. Cournier, M. Habib, A new linear algorithm for modular decomposition, LIRMM, University Montpellier (1995), Preliminary version in: Trees in Algebra and Programming-CAAP\u2019 94, LNCS 787 (1994) 68\u201384"},{"key":"51_CR24","unstructured":"E. Dahlhaus, J. Gustedt, R.M. McConnell, Efficient and practical modular decomposition, Tech. Report TU Berlin FB Mathematik, 524\/1996 (1996), in: Conference Proceedings 8th SODA (1997), 26\u201335"},{"key":"51_CR25","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01195324","volume":"9","author":"C. Simone De","year":"1993","unstructured":"C. De SIMONE, On the vertex packing problem, Graphs and Combinatorics 9 (1993) 19\u201330","journal-title":"Graphs and Combinatorics"},{"key":"51_CR26","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0166-218X(93)90032-J","volume":"41","author":"C. Simone De","year":"1993","unstructured":"C. De SIMONE, A. Sassano, Stability number of bull-and chair-free graphs, Discrete Applied Math. 41 (1993) 121\u2013129","journal-title":"Discrete Applied Math."},{"key":"51_CR27","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0012-365X(89)90268-9","volume":"73","author":"M. Farber","year":"1989","unstructured":"M. Farber, On diameters and radii of bridged graphs, Discrete Math. 73 (1989) 249\u2013260","journal-title":"Discrete Math."},{"key":"51_CR28","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0012-365X(93)90539-6","volume":"121","author":"J.-L. Fouquet","year":"1993","unstructured":"J.-L. Fouquet, A decomposition for a class of P\n                           5, -P\n                           5)-free graphs, Discrete Math. 121 (1993) 75\u201383","journal-title":"Discrete Math."},{"key":"51_CR29","first-page":"267","volume":"165\u2013166","author":"J.-L. Fouquet","year":"1997","unstructured":"J.-L. Fouquet, V. Giakoumakis On semi-P\n                           4-sparse graphs, Discrete Math. 165\u2013166 (1997) 267\u2013290","journal-title":"Discrete Math."},{"key":"51_CR30","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0012-365X(94)00155-X","volume":"146","author":"J.-L. Fouquet","year":"1995","unstructured":"J.-L. Fouquet, V. Giakoumakis, H. Thuillier, F. Maire, On graphs without P\n                           5 and -P\n                           5, Discrete Math. 146 (1995) 33\u201344","journal-title":"Discrete Math."},{"key":"51_CR31","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0166-218X(97)00093-0","volume":"80","author":"V. Giakoumakis","year":"1997","unstructured":"V. Giakoumakis, I. Rusu, Weighted parameters in (P\n                           5, -P\n                           5)-free graphs, Discrete Appl. Math. 80 (1997) 255\u2013261","journal-title":"Discrete Appl. Math."},{"key":"51_CR32","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S0304-3975(96)00220-4","volume":"180","author":"V. Giakoumakis","year":"1997","unstructured":"V. Giakoumakis, J.-M. Vanherpe, On Extended P\n                           4-Reducible and Extended P\n                           4-Sparse Graphs, Theoretical Computer Science 180 (1997) 269\u2013286","journal-title":"Theoretical Computer Science"},{"key":"51_CR33","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York 1980"},{"key":"51_CR34","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/3-540-46784-X_14","volume-title":"Intern. Workshop on Graph-Theoretic Concepts in Comp. Sci. WG\u201998","author":"M.C. Golumbic","year":"1999","unstructured":"M.C. Golumbic, U. Rotics, On the Clique-Width of Perfect Graph Classes, Intern. Workshop on Graph-Theoretic Concepts in Comp. Sci. WG\u201998, Lecture Notes in Comp. Sci. 1665 (1999) 135\u2013147"},{"key":"51_CR35","volume-title":"A Class of Perfect Graphs, Ms. Sc. Thesis","author":"C.T. Ho\u00e0ng","year":"1983","unstructured":"C.T. Ho\u00e0ng, A Class of Perfect Graphs, Ms. Sc. Thesis, School of Computer Science, McGill University, Montreal (1983)"},{"key":"51_CR36","volume-title":"Perfect Graphs, Ph. D. Thesis","author":"C.T. Ho\u00e0ng","year":"1985","unstructured":"C.T. Ho\u00e0ng, Perfect Graphs, Ph. D. Thesis, School of Computer Science, McGill University Montreal (1985)"},{"key":"51_CR37","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1002\/jgt.3190130407","volume":"13","author":"C.T. Ho\u00e0ng","year":"1989","unstructured":"C.T. Ho\u00e0ng, B. Reed, Some classes of perfectly orderable graphs, J. Graph Theory 13 (1989) 445\u2013463","journal-title":"J. Graph Theory"},{"key":"51_CR38","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(92)90036-A","volume":"35","author":"B. Jamison","year":"1992","unstructured":"B. Jamison, S. Olariu, A unique tree representation for P\n                           4-sparse graphs, Discrete Appl. Math. 35 (1992), 115\u2013129","journal-title":"Discrete Appl. Math."},{"key":"51_CR39","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0012-365X(99)00408-2","volume":"222","author":"V.V. Lozin","year":"2000","unstructured":"V.V. Lozin, Conic reduction of graphs for the stable set problem, Discrete Math. 222 (2000) 199\u2013211","journal-title":"Discrete Math."},{"key":"51_CR40","unstructured":"N.V.R. Mahadev, U.N. Peled, Threshold Graphs and Related Topics, Annals of Discrete Mathematics 56 (1995)"},{"key":"51_CR41","unstructured":"R.M. McConnell, J. Spinrad, Linear-time modular decomposition and efficient transitive orientation of comparability graphs, 5th. Ann. ACM-SIAM Symp. on Discrete Algorithms, Arlington, Virginia, 1994, 536\u2013543"},{"key":"51_CR42","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R.M. McConnell","year":"1999","unstructured":"R.M. McConnell, J. Spinrad, Modular decomposition and transitive orientation, Discrete Math. 201 (1999) 189\u2013241","journal-title":"Discrete Math."},{"key":"51_CR43","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"G.J. Minty","year":"1980","unstructured":"G.J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory (B) 28 (1980) 284\u2013304","journal-title":"J. Combin. Theory (B)"},{"key":"51_CR44","first-page":"257","volume":"19","author":"R.H. M\u00f6hring","year":"1984","unstructured":"R.H. M\u00f6hring, F.J. Radermacher, Substitution decomposition for discrete structures and connections with combinatorial optimization, Annals of Discrete Math. 19 (1984) 257\u2013356","journal-title":"Annals of Discrete Math."},{"key":"51_CR45","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0020-0190(90)90143-L","volume":"34","author":"S. Olariu","year":"1990","unstructured":"S. Olariu, On the closure of triangle-free graphs under substitution, Information Processing Letters 34 (1990) 97\u2013101","journal-title":"Information Processing Letters"},{"key":"51_CR46","first-page":"307","volume":"15","author":"S. Poljak","year":"1974","unstructured":"S. Poljak, A note on stable sets and colorings of graphs, Commun. Math. Univ. Carolinae 15 (1974) 307\u2013309","journal-title":"Commun. Math. Univ. Carolinae"},{"key":"51_CR47","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N. Sbihi","year":"1980","unstructured":"N. Sbihi, Algorithme de recherche d\u2019un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile, Discrete Math. 29 (1980) 53\u201376","journal-title":"Discrete Math."},{"key":"51_CR48","volume-title":"Representations of graphs, Book Manuscript","author":"J.P. Spinrad","year":"1998","unstructured":"J.P. Spinrad, Representations of graphs, Book Manuscript, Vanderbilt University, Nashville (TN) 1998"},{"key":"51_CR49","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S. Tsukiyama","year":"1977","unstructured":"S. Tsukiyama, M. Ide, H. Ariyoshi, I. Shirakawa, A new algorithm for generating all the maximal independent sets, SIAM J. Computing 6 (1977) 505\u2013517","journal-title":"SIAM J. Computing"},{"key":"51_CR50","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"M. Yannakakis, The complexity of the partial order dimension problem, SIAM J. Algebraic and Discrete Methods 3 (1982) 351\u2013358","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"51_CR51","unstructured":"I. Zverovich, Extension of hereditary classes with substitutions, Rutcor Research Report RRR 14-2001 (2001) \n                    http:\/\/rutcor.rutgers.edu\/~rrr"},{"key":"51_CR52","unstructured":"I.E. Zverovich, I.I. Zverovich, Extended (P\n                           5, -P\n                           5)-free graphs, Rutcor Research Report RRR 22-2001 (2001) \n                    http:\/\/rutcor.rutgers.edu\/~rrr"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T02:01:37Z","timestamp":1550714497000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_51","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}