A Generalization of Nemhauser and Trotter's Local Optimization Theorem.

DOI10.4230/LIPIcs.STACS.2009.1820zbMath1236.68086OpenAlexW2259918091MaRDI QIDQ5389995

Hannes Moser, Rolf Niedermeier, Michael R. Fellows, Jiong Guo

Publication date: 24 April 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_5868.html

zbMATH Keywords

computational complexitycombinatorial optimizationNP-hard problemsfixed-parameter tractabilitygraph problemsNemhauser-Trotter local optimization theoremW[2-completeness]

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items (5)

On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ Lower bounds on kernelization ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ On Making a Distinguished Vertex Minimum Degree by Vertex Deletion

This page was built for publication: A Generalization of Nemhauser and Trotter's Local Optimization Theorem.