Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction

DOI10.1016/j.dam.2008.06.026zbMath1197.05026OpenAlexW2021683664MaRDI QIDQ1026118

Anita Das, B. S. Panda

Publication date: 24 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.06.026

zbMATH Keywords

distance in graphsgraph algorithmstree spannerdirected path graphs

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms

Cites Work

• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Intersection graphs of paths in a tree
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Restrictions of minimum spanner problems
• The separator theorem for rooted directed vertex graphs
• Tree spanners on chordal graphs: complexity and algorithms
• Intersection graphs of vertex disjoint paths in a tree
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Optimal tree 3-spanners in directed path graphs
• Distributed Computing: A Locality-Sensitive Approach
• Tree Spanners
• On tree 3‐spanners in directed path graphs
• Tree spanners in planar graphs

This page was built for publication: Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction