A linear-time algorithm for paired-domination problem in strongly chordal graphs
From MaRDI portal
Publication:990092
DOI10.1016/j.ipl.2009.09.014zbMath1197.05142DBLPjournals/ipl/ChenLZ09OpenAlexW2015415084WikidataQ60630615 ScholiaQ60630615MaRDI QIDQ990092
Lei Chen, Zhenbing Zeng, Chang-hong Lu
Publication date: 2 September 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.09.014
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (21)
Computing a minimum paired-dominating set in strongly orderable graphs ⋮ Complexity of paired domination in AT-free and planar graphs ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ Vertices in all minimum paired-dominating sets of block graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Complexity of paired domination in at-free and planar graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs ⋮ A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph ⋮ Paired-domination in claw-free graphs with minimum degree at least three ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs ⋮ Complexity of distance paired-domination problem in graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ \(k\)-power domination in block graphs ⋮ Paired Domination in Graphs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Domination, independent domination, and duality in strongly chordal graphs
- Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- \(k\)-tuple domination in graphs
- Labeling algorithms for domination problems in sun-free chordal graphs
- Paired-domination of trees
- Doubly lexical ordering of dense 0--1 matrices
- Paired domination on interval and circular-arc 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
- Paired-domination in graphs
This page was built for publication: A linear-time algorithm for paired-domination problem in strongly chordal graphs
