Total domination in interval graphs

DOI10.1016/0020-0190(86)90112-2zbMath0604.05032OpenAlexW2078732465MaRDI QIDQ5903263

Alan A. Bertossi

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)90112-2

zbMATH Keywords

polynomial-time algorithminterval graphshortest path problemtotal dominating setacyclic directed network

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (17)

On the domatic number of interval graphs ⋮ A unified approach to domination problems on interval graphs ⋮ Total domination in interval graphs revisited ⋮ Weighted independent perfect domination on cocomparability graphs ⋮ Convexity of minimal total dominating functions in graphs ⋮ On the computational complexity of upper total domination ⋮ New sequential and parallel algorithms for interval graph recognition ⋮ The bottleneck independent domination on the classes of bipartite graphs and block graphs. ⋮ Dominating sets in perfect graphs ⋮ The harmonious coloring problem is NP-complete for interval and permutation graphs ⋮ Parallel algorithms on circular-arc graphs ⋮ Hardness results and approximation algorithm for total liar's domination in graphs ⋮ A survey of selected recent results on total domination in graphs ⋮ Counting dominating sets in generalized series-parallel 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
• Unnamed Item
• Dominating sets for split and bipartite graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the Algorithmic Complexity of Total Domination
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Total domination in graphs
• The NP-completeness column: An ongoing guide

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