A linear time algorithm to compute a dominating path in an AT-free graph

DOI10.1016/0020-0190(95)00021-4zbMath0875.68455OpenAlexW2003352119MaRDI QIDQ673002

Stephan Olariu, Derek Gordon Corneil, Lorna K. Stewart

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00021-4

zbMATH Keywords

AlgorithmsDominationAsteroidal triple-free graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (9)

On the minimum eccentricity isometric cycle problem ⋮ Computing a dominating pair in an asteroidal triple-free graph in linear time ⋮ Diametral path graphs ⋮ Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem ⋮ On linear and circular structure of (claw, net)-free graphs ⋮ Domination and total domination on asteroidal triple-free graphs ⋮ Linear time algorithms for dominating pairs in asteroidal triple-free graphs ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Treelike comparability graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tolerance graphs
• The complexity of regular subgraph recognition
• An optimal greedy heuristic to color interval graphs
• Trapezoid graphs and their coloring
• Domination on Cocomparability Graphs
• Representation of a finite graph by a set of intervals on the real line
• Connected domination and steiner set on asteroidal triple-free graphs
• Permutation Graphs and Transitive Graphs

This page was built for publication: A linear time algorithm to compute a dominating path in an AT-free graph