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

DOI10.1016/0020-0190(95)00021-4zbMATH Open0875.68455OpenAlexW2003352119MaRDI QIDQ673002FDOQ673002

Authors Stephan Olariu, Derek G. Corneil, Lorna 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)

Recommendations

• Computing a dominating pair in an asteroidal triple-free graph in linear time
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Domination and total domination on asteroidal triple-free graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• An optimal greedy heuristic to color interval graphs
• Connected domination and steiner set on asteroidal triple-free graphs
• Domination on Cocomparability Graphs
• Permutation Graphs and Transitive Graphs
• Representation of a finite graph by a set of intervals on the real line
• The complexity of regular subgraph recognition
• Tolerance graphs
• Trapezoid graphs and their coloring

Cited in

(13)

• Domination and total domination on asteroidal triple-free graphs
• Diametral path graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free 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
• Connected domination and steiner set on asteroidal triple-free graphs
• Treelike comparability graphs
• Hereditary dominating pair graphs
• Computing a dominating pair in an asteroidal triple-free graph in linear time
• On the minimum eccentricity isometric cycle problem
• Edge-dominating trails in AT-free graphs (extended abstract)
• Tree decomposition and discrete optimization problems: a survey
• Independent sets in asteroidal triple-free graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673002)