Approximation algorithm for minimum \(q\)-dominator partization problem
From MaRDI portal
Publication:6542935
DOI10.1142/s1793830922501889zbMATH Open1537.05008MaRDI QIDQ6542935
Publication date: 23 May 2024
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Coloring of graphs and hypergraphs (05C15) 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) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Dominator colorings in some classes of graphs
- On the complexity of minimum \(q\)-domination partization problems
- On the complexity of cd-coloring of graphs
- Dominated colorings of graphs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Parameterized and Exact Algorithms for Class Domination Coloring
- Algorithmic Aspects of Dominator Colorings in Graphs
- On the power of unique 2-prover 1-round games
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- A Greedy Heuristic for the Set-Covering Problem
- Vertex packings: Structural properties and algorithms
- Approximating Clique and Biclique Problems
- On the hardness of approximating minimization problems
- Analytical approach to parallel repetition
- Mathematical Foundations of Computer Science 2004
- Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes
This page was built for publication: Approximation algorithm for minimum \(q\)-dominator partization problem
