A Deterministic Approximation Algorithm for Maximum 2-Path Packing
スポンサーリンク
概要
- 論文の詳細を見る
This paper deals with the maximum-weight 2-path packing problem (M2PP), which is the problem of computing a set of vertex-disjoint paths of length 2 in a given edge-weighted complete graph so that the total weight of edges in the paths is maximized. Previously, Hassin and Rubinstein gave a randomized cubic-time approximation algorithm for M2PP which achieves an expected ratio of 35/67 - ε ≈ 0.5223 - ε for any constant ε > 0. We refine their algorithm and derandomize it to obtain a deterministic cubic-time approximation algorithm for the problem which achieves a better ratio (namely, 0.5265 - ε for any constant ε > 0).
- （社）電子情報通信学会の論文
- 2010-02-01
著者
-
CHEN Zhi-Zhong
Department of Mathematical Sciences, Tokyo Denki University
-
Chen Zhi-zhong
Department Of Mathematical Sciences Tokyo Denki University
-
Chen Zhi-zhong
Department Of Computer Science And Information Mathematics University Of Electro-communications
-
Tanahashi Ruka
Department Of Mathematical Sciences Tokyo Denki University
関連論文
- Parallel Algorithms for Maximal Linear Forests
- Study of Photocurrent Properties of GaN Ultraviolet Photoconductor Grown on 6H-SiC Substrate
- Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs
- More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling (New Aspects of Theoretical Computer Science)
- The Complexity of Selecting Maximal Solutions
- Finding Maximal Cycle-Free Subgraphs in Parallel(Fundamental Studies on Computational Complexity)
- A Deterministic Approximation Algorithm for Maximum 2-Path Packing
- Grammatical Characterizations of P and PSPACE
- Parallel Algorithms for the Maximal Tree Cover Problems