Publication:5389995
From MaRDI portal
DOI10.4230/LIPIcs.STACS.2009.1820zbMath1236.68086MaRDI QIDQ5389995
Michael R. Fellows, Rolf Niedermeier, Jiong Guo, Hannes Moser
Publication date: 24 April 2012
Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_5868.html
computational complexity; combinatorial optimization; NP-hard problems; fixed-parameter tractability; graph problems; Nemhauser-Trotter local optimization theorem; W[2-completeness]
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C07: Vertex degrees