Parameterized Algorithms for Generalized Domination

DOI10.1007/978-3-540-85097-7_11zbMath1168.05354OpenAlexW2132198511MaRDI QIDQ5505650

Venkatesh Raman, Saket Saurabh, Sriganesh Srihari

Publication date: 27 January 2009

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85097-7_11

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

(Total) vector domination for graphs with bounded branchwidth ⋮ Subexponential Fixed-Parameter Algorithms for Partial Vector Domination ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ Constant thresholds can make target set selection tractable ⋮ Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover ⋮ On bounded-degree vertex deletion parameterized by treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Approximation algorithms for combinatorial problems
• Threshold dominating sets and an improved characterization of \(W[2\)]
• On the existence of subexponential parameterized algorithms
• Parametrized complexity theory.
• A threshold of ln n for approximating set cover
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
• A note on domination in bipartite graphs
• Paths, Trees, and Flowers
• Improved Parameterized Upper Bounds for Vertex Cover

This page was built for publication: Parameterized Algorithms for Generalized Domination