A 7/3-Approximation for the Minimum Weight 3-Connected Spanning Subgraph Problem(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• 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≥2, and there are an O(n^2m) 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^2m) time.

• 社団法人電子情報通信学会の論文
• 2000-04-25

著者

• Seki K

  Iwate Univ. Morioka‐shi Jpn

• Nagamochi Hiroshi

  The Authors Are With The Department Of Applied Mathematics And Physics Faculty Of Informatics Kyoto

• SEKI Katsuhiro

  The authors are with the Department of Applied Mathematics and Physics, faculty of Informatics, Kyot

• IBARAKI Toshihide

  The authors are with the Department of Applied Mathematics and Physics, faculty of Informatics, Kyot

• Ibaraki Toshihide

  The Authors Are With The Department Of Applied Mathematics And Physics Faculty Of Informatics Kyoto

関連論文

• A 7/3-Approximation for the Minimum Weight 3-Connected Spanning Subgraph Problem(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク