On the complexity of variations of mixed domination on graphs†
From MaRDI portal
Publication:2958268
DOI10.1080/00207160.2015.1080356zbMath1355.05238OpenAlexW2295543873MaRDI QIDQ2958268
Publication date: 1 February 2017
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207160.2015.1080356
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- A natural family of optimization problems with arbitrarily small approximation thresholds
- On the mixed minus domination in graphs
- The algorithmic complexity of mixed domination in graphs
- Variations of \(Y\)-dominating functions on graphs
- On the signed edge domination number of graphs
- On the characterization of trees with signed edge domination numbers 1, 2, 3, or 4
- Characterizations of strongly chordal graphs
- Optimization, approximation, and complexity classes
- On total covers of graphs
- Strong elimination ordering of the total graph of a tree
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- A characterization of strongly chordal graphs
- On edge domination numbers of graphs
- On the mixed domination problem in graphs
- Doubly lexical ordering of dense 0--1 matrices
- A lower bound on the total signed domination numbers of graphs
- Some notes on signed edge domination in graphs
- Distance-hereditary graphs are clique-perfect
- Two classes of edge domination in graphs
- Minimum Edge Dominating Sets
- Proof verification and the hardness of approximation problems
- An approximation algorithm for the total covering problem
- Domination and location in acyclic graphs
- Three Partition Refinement Algorithms
- Edge Dominating Sets in Graphs
- Total matchings and total coverings of graphs
- Graph Classes: A Survey
- Signed mixed dominating functions in complete bipartite graphs
- On signed edge domination numbers of graphs
