Tree spanners for bipartite graphs and probe interval graphs
DOI10.1007/S00453-006-1209-YzbMATH Open1107.68062OpenAlexW2045824107MaRDI QIDQ868437FDOQ868437
Authors: Feodor F. Dragan, Hoàng-Oanh Le, 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
Recommendations
- Tree spanners for bipartite graphs and probe interval graphs.
- Spanners for bounded tree-length graphs
- On tree-\(t\)-spanners in graphs
- On tree-\(t\)-spanners in graphs
- Tree spanners of bounded degree graphs
- Spanning \(k\)-trees of bipartite graphs
- Graph-Theoretic Concepts in Computer Science
- Tree 3-spanners on interval, permutation and regular bipartite graphs
- Tree spanners on chordal graphs: complexity and algorithms
- Tree spanners in planar graphs
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (18)
- Parameterized complexity of the spanning tree congestion problem
- Tree \(t\)-spanners in outerplanar graphs via supply demand partition
- An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
- Spanners in sparse graphs
- Tree 3-spanners on generalized prisms of graphs
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- The minimum stretch spanning tree problem for typical graphs
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Complexity results for the spanning tree congestion problem
- Well-partitioned chordal graphs
- Optimality computation of the minimum stretch spanning tree problem
- Tree spanners on chordal graphs: complexity and algorithms
- Polynomial algorithms for sparse spanners on subcubic graphs
- Three problems on well-partitioned chordal graphs
- Tree spanners for bipartite graphs and probe interval graphs.
- Hardness and efficiency on minimizing maximum distances in spanning trees
- Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs
- Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
This page was built for publication: Tree spanners for bipartite graphs and probe interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868437)
