On the Complexity Landscape of the Domination Chain

DOI10.1007/978-3-319-29221-2_6zbMath1437.68070OpenAlexW2396130679MaRDI QIDQ2795935

Henning Fernau, Ljiljana Brankovic, Katrin Casel, Cristina Bazgan

Publication date: 23 March 2016

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-29221-2_6

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) 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) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (6)

Parsimonious computational completeness ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Invited talks ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ Irredundance ⋮ Extension and its price for the connected vertex cover problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• Combinatorics for smaller kernels: the differential of a graph
• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• Approximating the minimum maximal independence number
• Improved upper bounds for vertex cover
• Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
• Clean the graph before you draw it!
• Optimization, approximation, and complexity classes
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Some APX-completeness results for cubic graphs
• Inequalities relating domination parameters in cubic graphs
• Fast algorithms for min independent dominating set
• Improved non-approximability results for minimum vertex cover with density constraints
• The complexity of irredundant sets parameterized by size
• Computing the differential of a graph: hardness, approximability and exact algorithms
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• The domination parameters of cubic graphs
• On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
• Algorithmic Aspects of Upper Domination: A Parameterised Perspective
• Exact Algorithms for Maximum Independent Set
• A Faster Algorithm for Dominating Set Analyzed by the Potential Method
• Approximation Algorithms Inspired by Kernelization Methods
• The differential and the roman domination number of a graph
• A threshold of ln n for approximating set cover
• On the max min vertex cover Problem
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Stability, domination and irredundance in a graph
• A Greedy Heuristic for the Set-Covering Problem
• Properties of Hereditary Hypergraphs and Middle Graphs
• On Syntactic versus Computational Views of Approximability
• Irredundance and Maximum Degree in Graphs
• SOFSEM 2006: Theory and Practice of Computer Science
• A Roman domination chain

This page was built for publication: On the Complexity Landscape of the Domination Chain