Inapproximability of the Edge-Contraction Problem(<Special Section>Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
For a property π on graphs, the edge-contraction problem with respect to π is defined as a problem of finding a set of edges of minimum cardinality whose contraction results in a graph satisfying the property π. This paper gives a lower bound for the approximation ratio for the problem for any property π that is hereditary on contractions and determined by biconnected components.
- 社団法人電子情報通信学会の論文
- 2006-05-01
著者
-
Hirata Tomio
Graduate School of Information Science Nagoya University
-
Hirata Tomio
Graduate School Of Engineering Nagoya University
-
OTSUKI Hideaki
Department of Physics, Hirosaki University
-
大月 英明
Department Of Software Engineering Nanzan University
-
Otsuki Hideaki
Department Of Physics Hirosaki University
-
HIRATA Tomio
Department of Electronics, Nagoya University
-
HIRATA Tomio
Graduate School of Engineering, Nagoya University
-
OTSUKI Hideaki
Graduate School of Engineering, Nagoya University
関連論文
- D-1-9 集合基底問題の正規基底を求める発見的アルゴリズム(D-1.コンピュテーション,一般セッション)
- 集合基底問題の正規基底を求めるヒューリスティックアルゴリズム
- 4C3 AN ADAPTIVE MEMORY LAGRANGIAN HEURISTIC ALGORITHM BASED ON THE SET COVERING APPROACH FOR THE MULTICUT PROBLEM
- Gravitational Perturbation of Schwarzschild-De Sitter Spacetime and Its Quasi-Normal Modes : Astrophysics and Relativity
- Inapproximability of the Minimum Biclique Edge Partition Problem
- Inapproximability of the Edge-Contraction Problem(Discrete Mathematics and Its Applications)
- LA-005 辺縮約問題の近似困難性(A分野:モデル・アルゴリズム・プログラミング)
- MIN 3-SET COVERの近似困難性
- MIN 3-SET COVER の近似困難性
- Refined Computations for Points of the Form 2kP Based on Montgomery Trick
- An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem
- On Approximation Algorithms for Coloring k-Colorable Graphs