Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
From MaRDI portal
Publication:2304548
DOI10.1016/j.tcs.2020.01.007zbMath1435.68112arXiv1810.06872OpenAlexW3000119614MaRDI QIDQ2304548
Andrea Munaro, Bernard Ries, Esther Galby
Publication date: 12 March 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.06872
computational complexitytotal dominating setdually chordal graphsbounded mim-widthsemitotal dominating set
Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (11)
Semitotal domination on AT-free graphs and circle graphs ⋮ Bounding the mim‐width of hereditary graph classes ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Blocking total dominating sets via edge contractions ⋮ Distance Domination in Graphs ⋮ Using edge contractions to reduce the semitotal domination number ⋮ 2-OUTER-INDEPENDENT SEMITOTAL DOMINATION IN GRAPHS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Total domination and transformation
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- On graphs for which the connected domination number is at most the total domination number
- \textsc{max-cut} and containment relations in graphs
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
- A note on an induced subgraph characterization of domination perfect graphs
- Design and analysis of approximation algorithms
- Perfect graphs involving semitotal and semipaired domination
- Upper domination: towards a dichotomy through boundary properties
- Dominating sets for split and bipartite graphs
- The strong perfect graph theorem
- Words and graphs
- Domination in convex and chordal bipartite graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- Recent developments on graphs of bounded clique-width
- Characterizations of strongly chordal graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- The complexity of domination problems in circle graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Some APX-completeness results for cubic graphs
- Algorithmic aspects of semitotal domination in graphs
- Domination and total domination on asteroidal triple-free graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Perfectly relating the domination, total domination, and paired domination numbers of a graph
- Boundary classes for graph problems involving non-local properties
- 3-colouring for dually chordal graphs and generalisations
- Lower bounds on the mim-width of some graph classes
- Approximating clique-width and branch-width
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs
- Easy problems for tree-decomposable graphs
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Dually Chordal Graphs
- The Complexity of Multiterminal Cuts
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Perfect connected-dominant graphs
- Graphs with large total domination number
- Complexity and approximation ratio of semitotal domination in graphs
- Total Domination in Graphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Hardness of computing width parameters based on branch decompositions over the vertex set
This page was built for publication: Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
