Computing a minimum outer-connected dominating set for the class of chordal graphs

DOI10.1016/J.IPL.2013.05.001zbMATH Open1296.05188OpenAlexW2029336174MaRDI QIDQ2444768FDOQ2444768

Authors: J. Mark Keil, D. Pradhan 

Publication date: 11 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.05.001

Recommendations

• Complexity of total outer-connected domination problem in graphs
• Finding outer-connected dominating sets in interval graphs
• On the complexity of the minimum outer-connected dominating set problem in graphs
• Algorithm and hardness results for outer-connected dominating set in graphs
• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs

zbMATH Keywords

graph algorithmsouter-connected dominationdominationNP-completeproper interval graphundirected path graphdoubly chordal graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) 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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the outer-connected domination in graphs
• Graph Classes: A Survey
• The outer-connected domination number of a graph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Representations of chordal graphs as subtrees of a tree
• Dually Chordal Graphs
• Dominating sets for split and bipartite graphs
• A recognition algorithm for the intersection graphs of paths in trees
• Dominating Sets in Chordal Graphs
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• A characterisation of rigid circuit graphs
• A linear time recognition algorithm for proper interval graphs
• Variations of maximum-clique transversal sets on graphs
• Title not available (Why is that?)
• Doubly chordal graphs, steiner trees, and connected domination
• Variations of \(Y\)-dominating functions on graphs
• On the complexity of signed and minus total domination in graphs
• Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

Cited In (15)

• Algorithm and hardness results for outer-connected dominating set in graphs
• A greedy algorithm for the fault-tolerant outer-connected dominating set problem
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
• The outer-connected domination number of Sierpiński-like graphs
• Bounds for the connected domination number of maximal outerplanar graphs
• Intersection graphs of non-crossing paths
• Finding outer-connected dominating sets in interval graphs
• Title not available (Why is that?)
• Domination and its variants in split graphs \(-\text{P}\) versus NPC dichotomy
• Complexity of total outer-connected domination problem in graphs
• On the complexity of the minimum outer-connected dominating set problem in graphs
• The Outer-Paired Domination of Graphs
• On the complexity of the outer-connected bondage and the outer-connected reinforcement problems
• Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs

This page was built for publication: Computing a minimum outer-connected dominating set for the class of chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444768)