Vertex cover, dominating set and my encounters with parameterized complexity and Mike Fellows

DOI10.1007/978-3-642-30891-8_6MaRDI QIDQ2908533zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Parameterized Algorithms for Generalized Domination
• The birth and early years of parameterized complexity
• Parameterized complexity of Vertex Cover variants
• Sparse parameterized problems
• scientific article; zbMATH DE number 125608

Cites work

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

Cited in

(2)

• Fixed-parameter tractability, a prehistory
• The birth and early years of parameterized complexity

This page was built for publication: Vertex cover, dominating set and my encounters with parameterized complexity and Mike Fellows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908533)