On minimum intersection of two minimum dominating sets of interval graphs

DOI10.1016/S0166-218X(97)00014-0MaRDI QIDQ1377653zbMATH OpenFDO

Authors Maw-Shang Chang, Chung-Chang Hsu

Publication date 26 March 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

dominationgraph algorithmintersectioninterval graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Combinatorial optimization (90C27)

Review text

The paper gives linear time algorithms for finding two minimum (connected) dominating sets with minimum intersection for interval graphs. This problem was introduced by \textit{D. L. Grinstead} and \textit{P. J. Slater} [Discrete Math. 86, No. 1-3, 239-254 (1990; Zbl 0745.05057)].

Recommendations

• On minimum dominating sets with minimum intersection
• Total domination in interval graphs
• Total domination in interval graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs

Cites work

• A simple linear-time algorithm for computing the center of an interval graph
• A unified approach to domination problems on interval graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• An optimal greedy heuristic to color interval graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4085682 (Why is no real title available?)
• scientific article; zbMATH DE number 3675921 (Why is no real title available?)
• scientific article; zbMATH DE number 3625441 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Introduction to ``Topics on Domination
• Linear time transformations between combinatorial problems
• On minimum dominating sets with minimum intersection
• On the homogeneous representation of interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(8)

• Remarks about disjoint dominating sets
• On minimum dominating sets with minimum intersection
• Minimum dominating sets of intervals on lines
• Pairs of disjoint dominating sets and the minimum degree of graphs
• Minimum connected dominating sets of intervals on lines
• scientific article; zbMATH DE number 867715 (Why is no real title available?)
• Minimum dominating sets of intervals on lines
• On minimum intersections of certain secondary dominating sets in graphs

This page was built for publication: On minimum intersection of two minimum dominating sets of interval graphs

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