Tree Spanners for Bipartite Graphs and Probe Interval Graphs |
| |
Authors: | Andreas Brandstadt Feodor F. Dragan Hoang-Oanh Le Van Bang Le Ryuhei Uehara |
| |
Affiliation: | (1) Institut fur Theoretische Informatik, Fachbereich Informatik, Universitat Rostock, 18051, Rostock, Germany;(2) Department of Computer Science, Kent State University, Kent, OH 44242, USA;(3) School of Information Science, Japan Advanced Institute of Science and Technology, Asahidai 1-1, Nomi, Ishikawa 923-1292, Japan |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|