Academic Journal
Tree Spanners in Planar Graphs
| العنوان: | Tree Spanners in Planar Graphs |
|---|---|
| المؤلفون: | Sandor P. Fekete, Jana Kremer |
| المساهمون: | The Pennsylvania State University CiteSeerX Archives |
| المصدر: | ftp://ftp.zpr.uni-koeln.de/pub/paper/zpr98-313a.ps.gz |
| سنة النشر: | 1998 |
| المجموعة: | CiteSeerX |
| مصطلحات موضوعية: | graph spanners, planar graphs, distance in graphs, subgraphs, trees, complexity, polynomial algorithms |
| الوصف: | A tree t-spanner of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most t times their distance in G. Spanner problems have received some attention, mostly in the context of communication networks. It is known that for general unweighted graphs, the problem of deciding the existence of a tree t- spanner can be solved in polynomial time for t = 2, while it is NP-hard for any t 4; the case t = 3 is open, but has been conjectured to be hard. In this paper, we consider tree spanners in planar graphs. We show that even for planar unweighted graphs, it is NP-hard to determine the minimum t for which a tree t-spanner exists. On the other hand, we give a polynomial algorithm for any xed t that decides for planar unweighted graphs with bounded face length whether there is a tree t-spanner. Furthermore, we prove that it can be decided in polynomial time whether a planar unweighted graph has a tree t-spanner for t = 3. |
| نوع الوثيقة: | text |
| وصف الملف: | application/postscript |
| اللغة: | English |
| Relation: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9485 |
| الاتاحة: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9485 |
| Rights: | Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| رقم الانضمام: | edsbas.18726E32 |
| قاعدة البيانات: | BASE |
كن أول من يترك تعليقا!