A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
DOI10.1142/S1793830915500202zbMATH Open1326.05111OpenAlexW2095423548MaRDI QIDQ5261054FDOQ5261054
Authors:
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
Recommendations
dominationNP-completeplanar graphsproper interval graphsrestrained dominationchordal bipartite graphsundirected path graphscircle graphs
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Title not available (Why is that?)
- Computing a minimum outer-connected dominating set for the class of chordal graphs
- Graph Classes: A Survey
- Incidence matrices and interval graphs
- Restrained domination in graphs
- Restrained domination in trees
- Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- The NP-completeness of Steiner tree and dominating set for chordal bipartite 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
- The complexity of domination problems in circle graphs
- A linear time recognition algorithm for proper interval graphs
- NP-completeness and APX-completeness of restrained domination in graphs
- Restrained domination in claw-free graphs with minimum degree at least two
- Trees with equal domination and restrained domination numbers
- Restrained domination in unicyclic graphs
Cited In (8)
- Weighted restrained domination in subclasses of planar graphs
- Restrained and total restrained domination in cographs
- Restrained domination in some subclasses of chordal graphs
- Linear algorithm for domatic number problem on interval 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
- Injective coloring of some subclasses of bipartite graphs and chordal graphs
This page was built for publication: A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5261054)
