Optimal tree 3-spanners in directed path graphs

DOI10.1002/(SICI)1097-0037(199909)34:2%3C81::AID-NET1%3E3.0.CO;2-PMaRDI QIDQ4267388zbMATH OpenOpenAlexFDO

Authors Hoàng-Oanh Le, Van Bang Le

Publication date 2 May 2001

Full work available at URL https://doi.org/10.1002/(sici)1097-0037(199909)34:2%3C81::aid-net1%3E3.0.co;2-p

zbMATH Keywords

directed path graphstree 3-spanner

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• On tree 3‐spanners in directed path graphs
• Characterization and recognition of tree 3-spanner admissible directed path graphs of diameter three
• Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction
• Tree 3-Spanner in 2-sep Chordal Graphs: Characterization, Recognition, and Construction.
• Tree Spanners

Cites work

• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Graph spanners
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Tree Spanners

Cited in

(10)

• Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction
• Characterization and recognition of tree 3-spanner admissible directed path graphs of diameter three
• Tree spanners of bounded degree graphs
• Tree spanners on chordal graphs: complexity and algorithms
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• Tree 3-Spanner in 2-sep Chordal Graphs: Characterization, Recognition, and Construction.
• A linear time algorithm to construct a tree 4-spanner on trapezoid graphs
• An optimal parallel algorithm to construct a tree 3-spanner on interval graphs
• On tree 3‐spanners in directed path graphs
• Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms

This page was built for publication: Optimal tree 3-spanners in directed path graphs

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