{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T09:06:39Z","timestamp":1777539999637,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642192210","type":"print"},{"value":"9783642192227","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-19222-7_1","type":"book-chapter","created":{"date-parts":[[2011,3,14]],"date-time":"2011-03-14T08:03:12Z","timestamp":1300089792000},"page":"1-9","source":"Crossref","is-referenced-by-count":11,"title":["Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes"],"prefix":"10.1007","author":[{"given":"Konrad","family":"Dabrowski","sequence":"first","affiliation":[]},{"given":"Vadim","family":"Lozin","sequence":"additional","affiliation":[]},{"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[]},{"given":"Dieter","family":"Rautenbach","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-3","key":"1_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(02)00290-1","volume":"135","author":"V.E. Alekseev","year":"2004","unstructured":"Alekseev, V.E.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Appl. Math.\u00a0135(1-3), 3\u201316 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.dam.2003.09.003","volume":"145","author":"V.E. Alekseev","year":"2004","unstructured":"Alekseev, V.E., Lozin, V.V.: Augmenting graphs for independent sets. Discrete Appl. Math.\u00a0145(1), 3\u201310 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"9","key":"1_CR3","doi-asserted-by":"publisher","first-page":"842","DOI":"10.1073\/pnas.43.9.842","volume":"43","author":"C. Berge","year":"1957","unstructured":"Berge, C.: Two theorems in graph theory. Proc. Nat. Acad. Sci. USA\u00a043(9), 842\u2013844 (1957)","journal-title":"Proc. Nat. Acad. Sci. USA"},{"issue":"3","key":"1_CR4","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/S0166-218X(03)00221-X","volume":"131","author":"R. Boliac","year":"2003","unstructured":"Boliac, R., Lozin, V.V.: An augmenting graph approach to the stable set problem in P 5-free graphs. Discrete Appl. Math.\u00a0131(3), 567\u2013575 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"1-2","key":"1_CR5","first-page":"295","volume":"389","author":"A. Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt, A., Ho\u00e0ng, C.T.: On clique separators, nearly chordal graphs, and the maximum weight stable set problem. Theoret.\u00a0Comput.\u00a0Sci.\u00a0389(1-2), 295\u2013306 (2007)","journal-title":"Theoret.\u00a0Comput.\u00a0Sci."},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/978-3-540-70575-8_52","volume-title":"Automata, Languages and Programming","author":"D. Corneil","year":"2008","unstructured":"Corneil, D., Habib, M., Paul, C., Tedder, M.: Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 634\u2013645. Springer, Heidelberg (2008)"},{"issue":"2","key":"1_CR7","doi-asserted-by":"publisher","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. Theory of Computing Systems\u00a033(2), 125\u2013150 (2000)","journal-title":"Theory of Computing Systems"},{"issue":"4","key":"1_CR8","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1125-y","volume":"41","author":"E.D. Demaine","year":"2005","unstructured":"Demaine, E.D., Hajiaghayi, M., Thilikos, D.M.: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors. Algorithmica\u00a041(4), 245\u2013267 (2005)","journal-title":"Algorithmica"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Denley, T.: The independence number of graphs with large odd girth. Electron. J. Comb.\u00a01, R9 (1994)","DOI":"10.37236\/1189"},{"key":"1_CR10","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Canadian J. Math.\u00a017, 449\u2013467 (1965)","journal-title":"Canadian J. Math."},{"issue":"3","key":"1_CR12","first-page":"343","volume":"70","author":"A. Ehrenfeucht","year":"1990","unstructured":"Ehrenfeucht, A., Rozenberg, G.: Primitivity is hereditary for 2-structures. Theoret.\u00a0Comput.\u00a0Sci.\u00a070(3), 343\u2013358 (1990)","journal-title":"Theoret.\u00a0Comput.\u00a0Sci."},{"issue":"1","key":"1_CR13","first-page":"53","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theoret.\u00a0Comput.\u00a0Sci.\u00a0410(1), 53\u201361 (2009)","journal-title":"Theoret.\u00a0Comput.\u00a0Sci."},{"key":"1_CR14","series-title":"Texts in Theoretical Computer Science","volume-title":"Parameterized complexity theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Texts in Theoretical Computer Science. Springer, Berlin (2006)"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare graphen. Acta Math.\u00a0Acad.\u00a0Sci.\u00a0Hungar.\u00a018, 25\u201366 (1967)","journal-title":"Acta Math.\u00a0Acad.\u00a0Sci.\u00a0Hungar."},{"key":"1_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"issue":"3","key":"1_CR17","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0166-218X(79)90043-X","volume":"1","author":"M. Habib","year":"1979","unstructured":"Habib, M., Maurer, M.C.: On the X-join decomposition for undirected graphs. Discrete Appl.\u00a0Math.\u00a01(3), 201\u2013207 (1979)","journal-title":"Discrete Appl.\u00a0Math."},{"key":"1_CR18","unstructured":"Halld\u00f3rsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the Sixth SAIM-ACM Symposium on Discrete Algorithms, San Francisco, CA, pp. 160\u2013169 (1995)"},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/11847250_15","volume-title":"Parameterized and Exact Computation","author":"J. K\u00e1ra","year":"2006","unstructured":"K\u00e1ra, J., Kratochv\u00edl, J.: Fixed parameter tractability of Independent Set in segment intersection graphs. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 166\u2013174. Springer, Heidelberg (2006)"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.endm.2009.07.021","volume":"34","author":"V.V. Lozin","year":"2009","unstructured":"Lozin, V.V.: Parameterized complexity of the maximum independent set problem and the speed of hereditary properties. Electronic Notes in Discrete Mathematics\u00a034, 127\u2013131 (2009)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Lozin, V.V.: Stability preserving transformations of graphs. Annals of Operations Research (to appear) doi: 10.1007\/s10479-008-0395-1","DOI":"10.1007\/s10479-008-0395-1"},{"issue":"13","key":"1_CR22","doi-asserted-by":"publisher","first-page":"2517","DOI":"10.1016\/j.dam.2008.03.008","volume":"156","author":"V.V. Lozin","year":"2008","unstructured":"Lozin, V.V., Milani\u010d, M.: On finding augmenting graphs. Discrete Appl. Math.\u00a0156(13), 2517\u20132529 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"1-3","key":"1_CR23","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R.M. McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math.\u00a0201(1-3), 189\u2013241 (1999)","journal-title":"Discrete Math."},{"issue":"3","key":"1_CR24","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"G.J. Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Combin. Theory Ser.\u00a0B\u00a028(3), 284\u2013304 (1980)","journal-title":"J. Combin. Theory Ser.\u00a0B"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-94-009-5315-4_2","volume-title":"Graphs and Orders","author":"R.H. M\u00f6hring","year":"1985","unstructured":"M\u00f6hring, R.H.: Algorithmic aspects of comparability graphs and interval graphs. In: Rival, I. (ed.) Graphs and Orders, pp. 41\u2013101. D. Reidel, Boston (1985)"},{"issue":"2-3","key":"1_CR26","doi-asserted-by":"publisher","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.\u00a092(2-3), 177\u2013191 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1_CR27","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0166-218X(92)90041-8","volume":"35","author":"O.J. Murphy","year":"1992","unstructured":"Murphy, O.J.: Computing independent sets in graphs with large girth. Discrete Appl. Math.\u00a035(2), 167\u2013170 (1992)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1_CR28","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1002\/jgt.3190150108","volume":"15","author":"S. Olariu","year":"1991","unstructured":"Olariu, S.: On the homogeneous representations of interval graphs. J. Graph Theory\u00a015(1), 65\u201380 (1991)","journal-title":"J. Graph Theory"},{"key":"1_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/11785293_29","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"V. Raman","year":"2006","unstructured":"Raman, V., Saurabh, S.: Triangles, 4-Cycles and Parameterized $\\mbox{(In-)Tractability}$ . In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 304\u2013315. Springer, Heidelberg (2006)"},{"issue":"14","key":"1_CR30","doi-asserted-by":"publisher","first-page":"2768","DOI":"10.1016\/j.dam.2007.11.013","volume":"156","author":"M. Rao","year":"2008","unstructured":"Rao, M.: Solving some NP-complete problems using split decomposition. Discrete Appl. Math.\u00a0156(14), 2768\u20132780 (2008)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19222-7_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,17]],"date-time":"2020-06-17T08:46:29Z","timestamp":1592383589000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19222-7_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642192210","9783642192227"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19222-7_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}