Tree Spanners for Bipartite Graphs and Probe Interval Graphs
| Autor: | Hoang-Oanh Le, Feodor F. Dragan, Van Bang Le, Andreas Brandstädt, Ryuhei Uehara |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Interval bigraph
Block graph Discrete mathematics Trémaux tree K-ary tree General Computer Science Applied Mathematics Computer Science::Computational Geometry Tree-depth Complete bipartite graph NP-completeness Computer Science Applications Probe interval graph Combinatorics Tree spanner Pathwidth Chordal graph Chordal bipartite graph Gomory–Hu tree Computer Science::Data Structures and Algorithms Mathematics |
| Zdroj: | Algorithmica. 47:27-51 |
| ISSN: | 1432-0541 0178-4617 |
| DOI: | 10.1007/s00453-006-1209-y |
| Popis: | A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in (m log n) time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink