2024-03-29T14:34:28Z
https://nagoya.repo.nii.ac.jp/oai
oai:nagoya.repo.nii.ac.jp:00013174
2023-01-16T04:00:16Z
320:321:322
Inapproximability of the Minimum Biclique Edge Partition Problem
OTSUKI, Hideaki
HIRATA, Tomio
open access
Copyright (C) 2010 IEICE
biclique
edge partition
NP-hard
inapproximability
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.
Institute of Electronics, Information and Communication Engineers
2010-02-01
eng
journal article
VoR
http://hdl.handle.net/2237/15069
https://nagoya.repo.nii.ac.jp/records/13174
http://www.ieice.org/jpn/trans_online/index.html
0916-8532
IEICE transactions on information and systems
E93-D
2
290
292
https://nagoya.repo.nii.ac.jp/record/13174/files/468.pdf
application/pdf
157.7 kB
2018-02-20