{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T15:52:54Z","timestamp":1768319574825,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540230717","type":"print"},{"value":"9783540286394","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-28639-4_15","type":"book-chapter","created":{"date-parts":[[2010,9,20]],"date-time":"2010-09-20T20:25:35Z","timestamp":1285014335000},"page":"162-173","source":"Crossref","is-referenced-by-count":47,"title":["A Structural View on Parameterizing Problems: Distance from Triviality"],"prefix":"10.1007","author":[{"given":"Jiong","family":"Guo","sequence":"first","affiliation":[]},{"given":"Falk","family":"H\u00fcffner","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"15_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for Dominating Set and related problems on planar graphs. Algorithmica\u00a033(4), 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-44683-4_11","volume-title":"Mathematical Foundations of Computer Science 2001","author":"J. Alber","year":"2001","unstructured":"Alber, J., Fan, H., Fellows, M.R., Fernau, H., Niedermeier, R., Rosamond, F., Stege, U.: Refined search tree technique for Dominating Set on planar graphs. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 111\u2013122. Springer, Heidelberg (2001)"},{"key":"15_CR3","unstructured":"Bodlaender, H.L.: Classes of graphs with bounded treewidth. Technical Report RUU-CS-86-22, Dept. of Computer Sci., Utrecht University (1986)"},{"key":"15_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BFb0029946","volume-title":"Mathematical Foundations of Computer Science 1997","author":"H.L. Bodlaender","year":"1997","unstructured":"Bodlaender, H.L.: Treewidth: Algorithmic techniques and results. In: Privara, I., Ru\u017ei\u010dka, P. (eds.) MFCS 1997. LNCS, vol.\u00a01295, pp. 19\u201336. Springer, Heidelberg (1997)"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","volume":"147","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Wareham, H.T.: The parameterized complexity of the longest common subsequence problem. Theoretical Computer Science\u00a0147, 31\u201354 (1995)","journal-title":"Theoretical Computer Science"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters\u00a058, 171\u2013176 (1996)","journal-title":"Information Processing Letters"},{"issue":"1","key":"15_CR7","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L. Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of Vertex Colouring. Discrete Applied Mathematics\u00a0127(1), 415\u2013429 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex Cover: Further observations and further improvements. J. Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"key":"15_CR9","first-page":"830","volume-title":"Proc. 15th SODA","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M.T., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs. In: Proc. 15th SODA, pp. 830\u2013839. SIAM, Philadelphia (2004)"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Downey, R.G.: Parameterized complexity for the skeptic. In: Proc. 18th IEEE Annual Conference on Computational Complexity, pp. 147\u2013169 (2003)","DOI":"10.1109\/CCC.2003.1214417"},{"key":"15_CR11","doi-asserted-by":"crossref","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. Springer, Heidelberg (1999); 4 The latter being of particular interest when attacking W[1]-hard problems"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/3-540-45471-3_19","volume-title":"Algorithm Theory - SWAT 2002","author":"J. Ellis","year":"2002","unstructured":"Ellis, J., Fan, H., Fellows, M.R.: The Dominating Set problem is fixed parameter tractable for graphs of bounded genus. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol.\u00a02368, pp. 180\u2013189. Springer, Heidelberg (2002)"},{"key":"15_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-39890-5_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.R. Fellows","year":"2003","unstructured":"Fellows, M.R.: Blow-ups, win\/win\u2019s, and crown rules: Some new directions in FPT. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 1\u201312. Springer, Heidelberg (2003)"},{"key":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-540-45078-8_44","volume-title":"Algorithms and Data Structures","author":"M.R. Fellows","year":"2003","unstructured":"Fellows, M.R.: New directions and new challenges in algorithm design and complexity, parameterized. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 505\u2013520. Springer, Heidelberg (2003)"},{"key":"15_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/3-540-44849-7_17","volume-title":"Proc. 5th CIAC 2003","author":"J. Gramm","year":"2003","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: Fixed-parameter algorithms for clique generation. In: CIAC 2003. LNCS, vol.\u00a02653, pp. 108\u2013119. Springer, Heidelberg (2003); To appear in Theory of Computing Systems."},{"issue":"4","key":"15_CR16","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s00453-004-1090-5","volume":"39","author":"J. Gramm","year":"2004","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica\u00a039(4), 321\u2013347 (2004)","journal-title":"Algorithmica"},{"key":"15_CR17","unstructured":"Guo, J., Niedermeier, R.: Exact algorithms and applications for Tree-like Weighted Set Cover (June 2004) (manuscript)"},{"issue":"4","key":"15_CR18","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1137\/S0895480100375831","volume":"15","author":"T.W. Haynes","year":"2002","unstructured":"Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM J. Discrete Math.\u00a015(4), 519\u2013529 (2002)","journal-title":"SIAM J. Discrete Math."},{"key":"15_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/978-3-540-27798-9_30","volume-title":"Computing and Combinatorics","author":"M. Hoffmann","year":"2004","unstructured":"Hoffmann, M., Okamoto, Y.: The traveling salesman problem with few inner points. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol.\u00a03106, pp. 268\u2013277. Springer, Heidelberg (2004)"},{"key":"15_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-540-30559-0_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Juedes","year":"2004","unstructured":"Juedes, D., Chor, B., Fellows, M.R.: Linear kernels in linear time, or How to save k colors in O(n2) steps. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 257\u2013269. Springer, Heidelberg (2004) (to appear)"},{"key":"15_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-540-28629-5_4","volume-title":"Mathematical Foundations of Computer Science 2004","author":"R. Niedermeier","year":"2004","unstructured":"Niedermeier, R.: Ubiquitous parameterization\u2014invitation to fixed-parameter algorithms. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol.\u00a03153, pp. 84\u2013103. Springer, Heidelberg (2004) (to appear)"},{"issue":"2","key":"15_CR22","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0196-6774(03)00005-1","volume":"47","author":"R. Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for Weighted Vertex Cover. J. Algorithms\u00a047(2), 63\u201377 (2003)","journal-title":"J. Algorithms"},{"key":"15_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/3-540-44634-6_8","volume-title":"Algorithms and Data Structures","author":"N. Nishimura","year":"2001","unstructured":"Nishimura, N., Ragde, P., Thilikos, D.M.: Fast fixed-parameter tractable algorithms for nontrivial generalizations of Vertex Cover. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol.\u00a02125, pp. 75\u201386. Springer, Heidelberg (2001); To appear in Discrete Applied Mathematics"},{"key":"15_CR24","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci.\u00a043, 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"15_CR25","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K. Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet Shortest Common Supersequence and Longest Common Subsequence problems. J. Comput. Syst. Sci.\u00a067(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR26","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II: Algorithmic aspects of treewidth. J. Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"15_CR27","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J.M. Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms\u00a07, 425\u2013440 (1986)","journal-title":"J. Algorithms"},{"key":"15_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/3-540-45071-8_55","volume-title":"Computing and Combinatorics","author":"S. Szeider","year":"2003","unstructured":"Szeider, S.: Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol.\u00a02697, pp. 548\u2013558. Springer, Heidelberg (2003)"},{"issue":"3","key":"15_CR29","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput.\u00a013(3), 566\u2013579 (1984)","journal-title":"SIAM J. Comput."},{"key":"15_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1007\/3-540-57155-8_284","volume-title":"Algorithms and Data Structures","author":"J.A. Telle","year":"1993","unstructured":"Telle, J.A., Proskurowski, A.: Practical algorithms on partial k-trees with an application to domination-like problems. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol.\u00a0709, pp. 610\u2013621. Springer, Heidelberg (1993)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-28639-4_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:29:55Z","timestamp":1620012595000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-28639-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230717","9783540286394"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-28639-4_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}