Tree spanners for bipartite graphs and probe interval graphs

DOI10.1007/s00453-006-1209-yzbMath1107.68062OpenAlexW2045824107MaRDI QIDQ868437

Hoàng-Oanh Le, Feodor F. Dragan, Van Bang Le, Ryuhei Uehara, Andreas Brandstädt

Publication date: 5 March 2007

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-006-1209-y

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs ⋮ Well-partitioned chordal graphs ⋮ Optimality computation of the minimum stretch spanning tree problem ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Hardness and efficiency on minimizing maximum distances in spanning trees ⋮ Three problems on well-partitioned chordal graphs ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Spanners in sparse graphs ⋮ Tree \(t\)-spanners in outerplanar graphs via supply demand partition ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ Complexity Results for the Spanning Tree Congestion Problem ⋮ The minimum stretch spanning tree problem for typical graphs ⋮ An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs

This page was built for publication: Tree spanners for bipartite graphs and probe interval graphs