Total domination in interval graphs

DOI10.1016/0020-0190(86)90022-0zbMath0595.05063OpenAlexW2062262038MaRDI QIDQ5903156

J. Mark Keil

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90022-0

zbMATH Keywords

interval graphtotal dominationtotal dominating setlinear algorithm

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (14)

Finding the minimum bandwidth of an interval graph ⋮ A unified approach to domination problems on interval graphs ⋮ Total domination in interval graphs revisited ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ Weighted independent perfect domination on cocomparability graphs ⋮ Total domination in block graphs ⋮ A linear time algorithm for liar's domination problem in proper interval graphs ⋮ The bottleneck independent domination on the classes of bipartite graphs and block graphs. ⋮ Dominating sets in perfect graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ A survey of selected recent results on total domination in graphs ⋮ Achromatic number is NP-complete for cographs and interval graphs ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Finding Hamiltonian circuits in interval graphs
• Clustering and domination in perfect graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A linear algorithm for the domination number of a series-parallel graph
• Representation of a finite graph by a set of intervals on the real line
• On the Algorithmic Complexity of Total Domination
• Domination in permutation graphs
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Dominating Sets in Chordal Graphs
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Total domination in interval graphs