Optimal tree 3-spanners in directed path graphs

DOI<81::AID-NET1>3.0.CO;2-P 10.1002/(SICI)1097-0037(199909)34:2<81::AID-NET1>3.0.CO;2-PzbMath0959.90065OpenAlexW2019748419MaRDI QIDQ4267388

Van Bang Le, Hoàng-Oanh Le

Publication date: 2 May 2001

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199909)34:2<81::aid-net1>3.0.co;2-p

zbMATH Keywords

directed path graphstree 3-spanner

Mathematics Subject Classification ID

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

Related Items

Tree spanners on chordal graphs: complexity and algorithms ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ Tree spanners of bounded degree graphs ⋮ Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction ⋮ Additive sparse spanners for graphs with bounded length of largest induced cycle

Cites Work

• Tree 3-spanners on interval, permutation and regular bipartite graphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• Graph spanners
• Distance Approximating Trees for Chordal and Dually Chordal Graphs
• Tree Spanners
• Unnamed Item