Domination chain: characterisation, classical complexity, parameterised complexity and approximability
From MaRDI portal
Publication:2181241
DOI10.1016/j.dam.2019.10.005zbMath1439.05174OpenAlexW2981213845MaRDI QIDQ2181241
Henning Fernau, Cristina Bazgan, Ljiljana Brankovic, Katrin Casel
Publication date: 18 May 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://basepub.dauphine.psl.eu/handle/123456789/22260
special graph classesparameterised complexityapproximation complexitydomination chainclassical complexity
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
Recognizing well-dominated graphs is coNP-complete ⋮ Unnamed Item ⋮ Algorithmic aspects of upper edge domination ⋮ An improved exact algorithm for minimum dominating set in chordal graphs ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ On the complexity of solution extension of optimization problems
Cites Work
- Fundamentals of parameterized complexity
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Combinatorics for smaller kernels: the differential of a graph
- On the max min vertex cover problem
- On the complexity of embedding planar graphs to minimize certain distance measures
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Approximating the minimum maximal independence number
- Improved upper bounds for vertex cover
- On domination and independent domination numbers of a graph
- Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs
- \(\Delta \)-list vertex coloring in linear time
- Data reductions and combinatorial bounds for improved approximation algorithms
- Clean the graph before you draw it!
- A note on total domination
- Optimization, approximation, and complexity classes
- Some simplified NP-complete graph problems
- A partial k-arboretum of graphs with bounded treewidth
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- The sequence of upper and lower domination, independence and irredundance numbers of a graph
- A special planar satisfiability problem and a consequence of its NP- completeness
- Some APX-completeness results for cubic graphs
- The many facets of upper domination
- Computational study on a PTAS for planar dominating set problem
- Inequalities relating domination parameters in cubic graphs
- Fixed parameter algorithms for DOMINATING SET and related problems on planar 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
- Exact algorithms for maximum independent set
- 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
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
- Cycle Domination, Independence and Irredundance in graphs
- A Faster Algorithm for Dominating Set Analyzed by the Potential Method
- The differential and the roman domination number of a graph
- A threshold of ln n for approximating set cover
- Subexponential Algorithms for Unique Games and Related Problems
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- 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
- Enclaveless sets and MK-Systems
- A Greedy Heuristic for the Set-Covering Problem
- Properties of Hereditary Hypergraphs and Middle Graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- On Syntactic versus Computational Views of Approximability
- Approximation algorithms for NP-complete problems on planar graphs
- Irredundance and Maximum Degree in Graphs
- On approximation properties of the Independent set problem for degree 3 graphs
- Analytical approach to parallel repetition
- Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
- SOFSEM 2006: Theory and Practice of Computer Science
- A Roman domination chain
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
