Inapproximability of the Minimum Biclique Edge Partition Problem
スポンサーリンク
概要
- 論文の詳細を見る
For a graph G, a biclique edge partition SBP(G) is a collection of bicliques (complete bipartite subgraphs) Bi such that each edge of G is contained in exactly one Bi. The Minimum Biclique Edge Partition Problem (MBEPP) asks for SBP(G) with the minimum size. In this paper, we show that for arbitrary small ε > 0, (6053/6052 - ε)-approximation of MBEPP is NP-hard.
- （社）電子情報通信学会の論文
- 2010-02-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