The search functionality is under construction.

The search functionality is under construction.

We consider the problem of finding a minimum weight *k*-connected spanning subgraph of a given edge-weighted graph *G* for *k*=3. The problem is known to be NP-hard for *k**O*(*n*^{2}*m*) time 3-approximation algorithm due to Nutov and Penn and an *O*(*n*^{8}) time 2-approximation algorithm due to Dinitz and Nutov, where *n* and *m* are the numbers of vertices and edges in *G*, respectively. In this paper, we present a 7/3-approximation algorithm which runs in *O*(*n*^{2}*m*) time.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.687-691

- Publication Date
- 2000/04/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Hiroshi NAGAMOCHI, Katsuhiro SEKI, Toshihide IBARAKI, "A 7/3-Approximation for the Minimum Weight 3-Connected Spanning Subgraph Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 4, pp. 687-691, April 2000, doi: .

Abstract: We consider the problem of finding a minimum weight *k*-connected spanning subgraph of a given edge-weighted graph *G* for *k*=3. The problem is known to be NP-hard for *k**O*(*n*^{2}*m*) time 3-approximation algorithm due to Nutov and Penn and an *O*(*n*^{8}) time 2-approximation algorithm due to Dinitz and Nutov, where *n* and *m* are the numbers of vertices and edges in *G*, respectively. In this paper, we present a 7/3-approximation algorithm which runs in *O*(*n*^{2}*m*) time.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_687/_p

Copy

@ARTICLE{e83-a_4_687,

author={Hiroshi NAGAMOCHI, Katsuhiro SEKI, Toshihide IBARAKI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={A 7/3-Approximation for the Minimum Weight 3-Connected Spanning Subgraph Problem},

year={2000},

volume={E83-A},

number={4},

pages={687-691},

abstract={We consider the problem of finding a minimum weight *k*-connected spanning subgraph of a given edge-weighted graph *G* for *k*=3. The problem is known to be NP-hard for *k**O*(*n*^{2}*m*) time 3-approximation algorithm due to Nutov and Penn and an *O*(*n*^{8}) time 2-approximation algorithm due to Dinitz and Nutov, where *n* and *m* are the numbers of vertices and edges in *G*, respectively. In this paper, we present a 7/3-approximation algorithm which runs in *O*(*n*^{2}*m*) time.

keywords={},

doi={},

ISSN={},

month={April},}

Copy

TY - JOUR

TI - A 7/3-Approximation for the Minimum Weight 3-Connected Spanning Subgraph Problem

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 687

EP - 691

AU - Hiroshi NAGAMOCHI

AU - Katsuhiro SEKI

AU - Toshihide IBARAKI

PY - 2000

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E83-A

IS - 4

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - April 2000

AB - We consider the problem of finding a minimum weight *k*-connected spanning subgraph of a given edge-weighted graph *G* for *k*=3. The problem is known to be NP-hard for *k**O*(*n*^{2}*m*) time 3-approximation algorithm due to Nutov and Penn and an *O*(*n*^{8}) time 2-approximation algorithm due to Dinitz and Nutov, where *n* and *m* are the numbers of vertices and edges in *G*, respectively. In this paper, we present a 7/3-approximation algorithm which runs in *O*(*n*^{2}*m*) time.

ER -