Tree 3-spanners on interval, permutation and regular bipartite graphs
From MaRDI portal
Publication:671393
DOI10.1016/0020-0190(96)00078-6zbMath0900.68332OpenAlexW1988646256WikidataQ126588256 ScholiaQ126588256MaRDI QIDQ671393
M. S. Madanlal, C. Pandu Rangan, G. Venkatesan
Publication date: 27 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(96)00078-6
Related Items (23)
Tree spanners on chordal graphs: complexity and algorithms ⋮ Well-partitioned chordal graphs ⋮ Eccentricity Approximating Trees ⋮ Spanners for bounded tree-length graphs ⋮ Restrictions of minimum spanner problems ⋮ Eccentricity approximating trees ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Tree spanners of bounded degree graphs ⋮ Three problems on well-partitioned chordal graphs ⋮ Minimum spanners of butterfly graphs ⋮ Hardness and efficiency on \(t\)-admissibility for graph operations ⋮ Tree \(t\)-spanners in outerplanar graphs via supply demand partition ⋮ 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 ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ The minimum stretch spanning tree problem for typical graphs ⋮ Optimal tree 3-spanners in directed path graphs ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction ⋮ Additive tree 2-spanners of permutation graphs ⋮ Additive sparse spanners for graphs with bounded length of largest induced cycle
Cites Work
This page was built for publication: Tree 3-spanners on interval, permutation and regular bipartite graphs
