Approximation algorithm for minimum q-dominator partization problem

DOI10.1142/S1793830922501889MaRDI QIDQ6542935zbMATH OpenFDO

Authors Sayani Das, Sounaka Mishra

Publication date 23 May 2024

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S1793830922501889

zbMATH Keywords

2-dominator partization3-dominator partizationapproximation algorithmAPX-hardnode deletion

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• On the complexity of minimum \(q\)-domination partization problems
• Algorithmic aspects of dominator colorings in graphs
• Lower bounds on approximating some variations of vertex coloring problem over restricted graph classes
• Dominator colorings in some classes of graphs
• Dominated colorings of graphs

Cites work

• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• 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

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)