On minimum intersection of two minimum dominating sets of interval graphs

DOI10.1016/S0166-218X(97)00014-0zbMath0887.05047MaRDI QIDQ1377653

Chung-Chang Hsu, Maw-Shang Chang

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

graph algorithmdominationinterval graphintersection

Mathematics Subject Classification ID

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

Related Items (2)

Pairs of disjoint dominating sets and the minimum degree of graphs ⋮ Remarks about disjoint dominating sets

Cites Work

• Introduction to ``Topics on Domination
• An optimal greedy heuristic to color interval graphs
• A unified approach to domination problems on interval graphs
• On minimum dominating sets with minimum intersection
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A simple linear-time algorithm for computing the center of an interval graph
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Linear time transformations between combinatorial problems
• On the homogeneous representation of interval graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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