Tree -spanners in outerplanar graphs via supply demand partition

详细信息    查看全文

• 作者：N.S. Narayanaswamy^a ; ^{swamy@cse.iitm.ac.in" class="auth_mail" title="E-mail the corresponding author} ; G. Ramakrishna^a ; ^b ; ^{rama.vikram@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Tree tt-spanner ; Minimum stretch spanning tree ; Supply&ndash ; demand tree partition ; Outerplanar graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2015
• 出版时间：20 November 2015
• 年：2015
• 卷：195
• 期：Complete
• 页码：104-109
• 全文大小：404 K

文摘

A tree  t$t$-spanner   of an unweighted graph G$G$ is a spanning tree T$T$ such that for every two vertices their distance in T$T$ is at most t$t$ times their distance in G$G$. Given an unweighted graph G$G$ and a positive integer t$t$ as input, the Treet$t$-spanner problem is to compute a tree t$t$-spanner of G$G$ if one exists. This decision problem is known to be NP-complete even in the restricted class of unweighted planar graphs. We present a linear-time reduction from Treet$t$-spanner in outerplanar graphs to the supply–demand tree partition problem. Based on this reduction, we obtain a linear-time algorithm to solve Treet$t$-spanner in outerplanar graphs. Consequently, we show that the minimum value of t$t$ for which an input outerplanar graph on n$n$ vertices has a tree t$t$-spanner can be found in O(nlogn)$O(nlogn)$ time.