Algorithmic aspects of semitotal domination in graphs

DOI10.1016/j.tcs.2018.09.019zbMath1418.68169arXiv1711.10891OpenAlexW2963893664MaRDI QIDQ1731849

Michael A. Henning, Arti Pandey

Publication date: 14 March 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.10891

zbMATH Keywords

graph algorithmapproximation algorithmbipartite graphschordal graphsNP-completedominationinterval graphsAPX-completesemitotal domination

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (22)

Complexity issues of perfect secure domination in graphs ⋮ Semipaired Domination in Some Subclasses of Chordal Graphs ⋮ Semitotal domination on AT-free graphs and circle graphs ⋮ Total vertex-edge domination in graphs: Complexity and algorithms ⋮ Complexity aspects of variants of independent Roman domination in graphs ⋮ Semitotal domination number of some graph operations ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From the strong differential to Italian domination in graphs ⋮ Algorithmic aspects of total Roman ${2}$-domination in graphs ⋮ Bounds on the semipaired domination number of graphs with minimum degree at least two ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ Algorithmic aspects of 2-secure domination in graphs ⋮ An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ The semitotal domination problem in block graphs ⋮ Semipaired domination in maximal outerplanar graphs ⋮ 2-OUTER-INDEPENDENT SEMITOTAL DOMINATION IN GRAPHS ⋮ Algorithmic complexity of weakly connected Roman domination in graphs ⋮ Algorithmic aspects of total Roman {3}-domination in graphs

Cites Work

• Vertices contained in all or in no minimum semitotal dominating set of a tree
• Domination in convex and chordal bipartite graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• A survey of selected recent results on total domination in graphs
• Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Some APX-completeness results for cubic graphs
• Edge weighting functions on semitotal dominating sets
• On matching and semitotal domination in graphs
• Total Domination in Graphs
• Semitotal domination in claw-free cubic graphs
• Dominating cliques in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithmic aspects of semitotal domination in graphs