Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree
| |
|
An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree
Hiroshi Nagamochi6  and Toshihide Ibaraki6
| (6) |
Kyoto University, Kyoto Japan, 606-8501 |
Abstract
Given a graph G=( V, E) and a tree T=( V, F) with E∩ F=∅ such that G + T = ( V, F∪ E) is 2-edge-connected, we consider the problem of finding a smallest 2-edge-connected spanning subgraph ( V, F∪
) of G + T containing T. The problem, which is known to be NP-hard, admits a 2-approximation algorithm. However, obtaining a factor better than 2
for this problem has been one of the main open problems in the graph augmentation problem. In this paper, we present an O
time
-approximation algorithm for this problem, where
and
This research was partially supported by the Scientific Grant-in-Aid from Ministry of Education, Science, Sports and Culture
of Japan, and the subsidy from the Inamori Foundation.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|