Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows

DOI10.1007/978-3-642-30891-8_6zbMath1358.68146OpenAlexW113281379MaRDI QIDQ2908533

Venkatesh Raman

Publication date: 5 September 2012

Published in: The Multivariate Algorithmic Revolution and Beyond (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-30891-8_6

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) History of computer science (68-03)

Cites Work

• Unnamed Item
• An improved fixed-parameter algorithm for vertex cover
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• On finding a minimum dominating set in a tournament
• On limited nondeterminism and the complexity of the V-C dimension
• Parameterized complexity of finding subgraphs with hereditary properties.
• On the existence of subexponential parameterized algorithms
• The complexity of irredundant sets parameterized by size
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• A Constructive Solution to a Tournament Problem

This page was built for publication: Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows