A linear-time algorithm for semitotal domination in strongly chordal graphs
From MaRDI portal
Publication:6110593
DOI10.1016/j.dam.2023.05.030zbMath1519.05235arXiv2109.02142OpenAlexW3196808644MaRDI QIDQ6110593
Arti Pandey, Anil Maheshwari, Vikash Tripathi
Publication date: 2 August 2023
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2109.02142
Nonnumerical algorithms (68W05) 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)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Perfect graphs involving semitotal and semipaired domination
- Domination, independent domination, and duality in strongly chordal graphs
- Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
- Semitotal domination on AT-free graphs and circle graphs
- Vertices contained in all or in no minimum semitotal dominating set of a tree
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- A survey of selected recent results on total domination in graphs
- \(k\)-tuple domination in graphs
- Labeling algorithms for domination problems in sun-free chordal graphs
- Algorithmic aspects of semitotal domination in graphs
- Edge weighting functions on semitotal dominating sets
- 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
- Doubly lexical ordering of dense 0--1 matrices
- On matching and semitotal domination in graphs
- Characterizations of totally balanced matrices
- Totally-Balanced and Greedy Matrices
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- Steiner trees, connected domination and strongly chordal graphs
- Doubly Lexical Orderings of Matrices
- Three Partition Refinement Algorithms
- Complexity and approximation ratio of semitotal domination in graphs
- Total Domination in Graphs
- Structures of Domination in Graphs
- Topics in Domination in Graphs
- Semitotal domination in claw-free cubic graphs
- Semitotal domination in claw-free cubic graphs
