Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs

DOI10.1137/S0097539795282377MaRDI QIDQ4268709zbMATH OpenOpenAlexFDO

Authors Stephan Olariu, Derek G. Corneil, Lorna Stewart

Publication date 28 October 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539795282377

zbMATH Keywords

algorithmsasteroidal triple-free graphslexicographic breadth-first searchdominating pairs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Computing a dominating pair in an asteroidal triple-free graph in linear time
• Asteroidal Triple-Free Graphs
• A linear time algorithm to compute a dominating path in an AT-free graph
• Domination and total domination on asteroidal triple-free graphs

Cited in

(42)

• Asteroidal triples of moplexes
• Separator orders in interval, cocomparability, and AT-free graphs
• Robinsonian matrices: recognition challenges
• Dominating Pair Graphs
• On end-vertices of lexicographic breadth first searches
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• On claw-free asteroidal triple-free graphs
• Diameter determination on restricted graph families
• On the power of graph searching for cocomparability graphs
• Boxicity and cubicity of asteroidal triple free graphs
• Approximability of the path-distance-width for AT-free graphs
• Hereditary dominating pair graphs
• On the minimum eccentricity isometric cycle problem
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Gallai-like characterization of strong cocomparability graphs
• The recognition problem of graph search trees
• Graph extremities defined by search algorithms
• On the domination search number
• On linear and circular structure of (claw, net)-free graphs
• Approximating the path-distance-width for AT-free graphs and graphs in related classes
• Recognizing graphs without asteroidal triples
• Recognizing graph search trees
• The diameter of AT‐free graphs
• Algorithms for graphs with small octopus
• Graph searches and their end vertices
• Induced matchings in asteroidal triple-free graphs
• Diametral path graphs
• Detecting induced minors in AT-free graphs
• Vertex ordering characterizations of graphs of bounded asteroidal number
• On the structure of graphs with bounded asteroidal number
• Domination and total domination on asteroidal triple-free graphs
• On the power of BFS to determine a graph's diameter
• Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications
• Graph Search Trees and Their Leaves
• Minimum eccentricity shortest paths in some structured graph classes
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Line-distortion, bandwidth and path-length of a graph
• Minimum eccentricity shortest path problem: an approximation algorithm and relation with the \(k\)-laminarity problem
• scientific article; zbMATH DE number 7511525 (Why is no real title available?)
• Computing a dominating pair in an asteroidal triple-free graph in linear time
• On the structure of graphs with bounded asteroidal number
• End-vertices of LBFS of (AT-free) bigraphs

This page was built for publication: Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs

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