Computing a dominating pair in an asteroidal triple-free graph in linear time

DOI10.1007/3-540-60220-8_76zbMath1502.68218OpenAlexW1578752392MaRDI QIDQ5057448

Stephan Olariu, Derek Gordon Corneil, Lorna K. Stewart

Publication date: 16 December 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60220-8_76

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Connected feedback vertex set on AT-free graphs ⋮ Convex and isometric domination of (weak) dominating pair graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm to compute a dominating path in an AT-free graph
• Tolerance graphs
• Trapezoid graphs and their coloring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Domination on Cocomparability Graphs
• Representation of a finite graph by a set of intervals on the real line
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Asteroidal Triple-Free Graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Connected domination and steiner set on asteroidal triple-free graphs
• Partial orders of dimension 2
• Permutation Graphs and Transitive Graphs

This page was built for publication: Computing a dominating pair in an asteroidal triple-free graph in linear time