Approximated Vertex Cover for Graphs with Perfect Matchings(<Special Section>Invited Papers from New Horizons in Computing)
スポンサーリンク
概要
- 論文の詳細を見る
Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general VERTEX COVER as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as 1.069+0.069d^^- where d^^- is the average degree of the given graph. In this paper we improve (ii). Namely we give a new VC-PM algorithm which greatly outperforms the above one and its approximation factor is roughly 2-(6.74)/(d^^-+6.28). Our algorithm also works for graphs with "large" matchings, although its approximation factor is degenerated.
- 社団法人電子情報通信学会の論文
- 2006-08-01
著者
-
IWAMA KAZUO
School of Informatics, Kyoto University
-
Iwama Kazuo
School Of Informatics Kyoto University
-
Tsukiji Tatsuie
Department of Information Science, Tokyo Denki University
-
IMAMURA Tomokazu
School of Informatics, Kyoto University
-
Tsukiji Tatsuie
Department Of Information Science Tokyo Denki University
-
Tsukiji Tatsuie
Department Of Computer Science Tokyo Institute Of Technology
-
Imamura Tomokazu
School Of Informatics Kyoto University
関連論文
- Average/Worst-Case Gap of Quantum Query Complexities
- Recent Developments in Mesh Routing Algorithms(Special Issue on Algorithm Engineering : Surveys)
- Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs
- The Axis-bound CNN Problem(Algorithms and Data Structures)
- DS-1-2 Packing Squares with Profits into a Rectangle
- Approximated Vertex Cover for Graphs with Perfect Matchings(Invited Papers from New Horizons in Computing)
- DS-1-11 Reconstructing Strings from Substrings with Quantum Query
- ^^-Coloring Problem(Graphs and Networks)
- Some Lower Bounds of Cyclic Shift on Boolean Circuits (Special Section on Discrete Mathematics and Its Applications)