Approximation algorithm for minimum q-dominator partization problem
DOI10.1142/S1793830922501889zbMATH Open1537.05008MaRDI QIDQ6542935FDOQ6542935
Authors: Sayani Das, Sounaka Mishra 
Publication date: 23 May 2024
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)
Cites Work
- A Greedy Heuristic for the Set-Covering Problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Vertex packings: Structural properties and algorithms
- On the power of unique 2-prover 1-round games
- On the hardness of approximating minimization problems
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
- Analytical approach to parallel repetition
- Algorithmic aspects of dominator colorings in graphs
- Dominator colorings and safe clique partitions
- Dominated colorings of graphs
- Approximating Clique and Biclique Problems
- Mathematical Foundations of Computer Science 2004
- Dominator colorings in some classes of graphs
- On the complexity of cd-coloring of graphs
- Parameterized and exact algorithms for class domination coloring
- Domination integrity of middle graphs
- On the complexity of minimum \(q\)-domination partization problems
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6542935)
