Domination and total domination on asteroidal triple-free graphs

DOI10.1016/S0166-218X(99)00128-6zbMath0943.05063WikidataQ127343082 ScholiaQ127343082MaRDI QIDQ1962038

Dieter Kratsch

Publication date: 30 August 2000

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

zbMATH Keywords

dominating setasteroidal tripleAT-free graphspolynomial time algorithmstotal domination

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On claw-free asteroidal triple-free graphs ⋮ Semitotal domination on AT-free graphs and circle graphs ⋮ On the Minimum Eccentricity Shortest Path Problem ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Complexity of paired domination in AT-free and planar graphs ⋮ Independent sets in asteroidal triple-free graphs ⋮ On the minimum eccentricity shortest path problem ⋮ Complexity of paired domination in at-free and planar graphs ⋮ On conditional covering problem ⋮ Connected feedback vertex set on AT-free graphs ⋮ Algorithms for graphs with small octopus ⋮ Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs ⋮ On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size ⋮ Matching properties in total domination vertex critical graphs ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ A survey of selected recent results on total domination in graphs ⋮ Efficient algorithms for Roman domination on some classes of graphs ⋮ Induced disjoint paths in AT-free graphs ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ Domination problems on P₅-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Total domination and transformation
• A linear time algorithm to compute a dominating path in an AT-free graph
• Independence and domination in polygon graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Introduction to ``Topics on Domination
• Clustering and domination in perfect graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• Dominating sets in perfect graphs
• The complexity of domination problems in circle graphs
• Domination on Cocomparability Graphs
• On Hadwiger's Number and the Stability Number
• Domination in permutation graphs
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Asteroidal Triple-Free Graphs
• Independent sets in asteroidal triple-free graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
• Connected domination and steiner set on asteroidal triple-free graphs
• The NP-completeness column: An ongoing guide