Approximation algorithm for minimum q-dominator partization problem
From MaRDI portal
Publication:6542935
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)
Recommendations
Cites work
- A Greedy Heuristic for the Set-Covering Problem
- Algorithmic aspects of dominator colorings in graphs
- Analytical approach to parallel repetition
- Approximating Clique and Biclique Problems
- Dominated colorings of graphs
- Domination integrity of middle graphs
- Dominator colorings and safe clique partitions
- Dominator colorings in some classes of graphs
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes
- Mathematical Foundations of Computer Science 2004
- On the complexity of cd-coloring of graphs
- On the complexity of minimum \(q\)-domination partization problems
- On the hardness of approximating minimization problems
- On the power of unique 2-prover 1-round games
- Parameterized and exact algorithms for class domination coloring
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Vertex packings: Structural properties and algorithms
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
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)
