A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs

DOI10.1142/S1793830915500202zbMath1326.05111OpenAlexW2095423548MaRDI QIDQ5261054

No author found.

Publication date: 1 July 2015

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830915500202

zbMATH Keywords

planar graphsNP-completedominationrestrained dominationproper interval graphschordal bipartite graphsundirected path graphscircle graphs

Mathematics Subject Classification ID

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 (6)

Weighted restrained domination in subclasses of planar graphs ⋮ Restrained and total restrained domination in cographs ⋮ Injective coloring of some subclasses of bipartite graphs and chordal graphs ⋮ Restrained domination and its variants in extended supergrid graphs ⋮ A linear algorithm for double Roman domination of proper interval graphs ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs

Cites Work

• Unnamed Item
• NP-completeness and APX-completeness of restrained domination in graphs
• An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree
• Restrained domination in claw-free graphs with minimum degree at least two
• A linear time recognition algorithm for proper interval graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The complexity of domination problems in circle graphs
• Restrained domination in graphs
• Restrained domination in trees
• Incidence matrices and interval graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs
• Trees with equal domination and restrained domination numbers
• Graph Classes: A Survey
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Restrained domination in unicyclic graphs

This page was built for publication: A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs