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

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

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)

Cites Work

• Title not available (Why is that?)
• Domination on Cocomparability Graphs
• Representation of a finite graph by a set of intervals on the real line
• Trapezoid graphs and their coloring
• Title not available (Why is that?)
• Permutation Graphs and Transitive Graphs
• Title not available (Why is that?)
• An optimal greedy heuristic to color interval graphs
• The complexity of regular subgraph recognition
• Tolerance graphs
• Connected domination and steiner set on asteroidal triple-free graphs

Cited In (12)

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

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)