Tree spanners for bipartite graphs and probe interval graphs

DOI10.1007/S00453-006-1209-YMaRDI QIDQ868437zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(18)

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