A New Polynomial-Time Solvable Graph Class for the Minimum Biclique Edge Cover Problem
Summary :
The minimum biclique edge cover problem (MBECP) is NP-hard for general graphs. It is known that if we restrict an input graph to the bipartite domino-free class, MBECP can be solved within polynomial-time of input graph size. We show a new polynomial-time solvable graph class for MBECP that is characterized by three forbidden graphs, a domino, a gem and K4. This graph class allows that an input graph is non-bipartite, and includes the bipartite domino-free graph class properly.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.10 pp.1202-1205
- Publication Date
- 2020/10/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2019DMP0004
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- optimization
Authors
Hideaki OTSUKI
Nanzan University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hideaki OTSUKI, "A New Polynomial-Time Solvable Graph Class for the Minimum Biclique Edge Cover Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E103-A, no. 10, pp. 1202-1205, October 2020, doi: 10.1587/transfun.2019DMP0004.
Abstract: The minimum biclique edge cover problem (MBECP) is NP-hard for general graphs. It is known that if we restrict an input graph to the bipartite domino-free class, MBECP can be solved within polynomial-time of input graph size. We show a new polynomial-time solvable graph class for MBECP that is characterized by three forbidden graphs, a domino, a gem and K4. This graph class allows that an input graph is non-bipartite, and includes the bipartite domino-free graph class properly.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2019DMP0004/_p
Copy
@ARTICLE{e103-a_10_1202,
author={Hideaki OTSUKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A New Polynomial-Time Solvable Graph Class for the Minimum Biclique Edge Cover Problem},
year={2020},
volume={E103-A},
number={10},
pages={1202-1205},
abstract={The minimum biclique edge cover problem (MBECP) is NP-hard for general graphs. It is known that if we restrict an input graph to the bipartite domino-free class, MBECP can be solved within polynomial-time of input graph size. We show a new polynomial-time solvable graph class for MBECP that is characterized by three forbidden graphs, a domino, a gem and K4. This graph class allows that an input graph is non-bipartite, and includes the bipartite domino-free graph class properly.},
keywords={},
doi={10.1587/transfun.2019DMP0004},
ISSN={1745-1337},
month={October},}
Copy
TY - JOUR
TI - A New Polynomial-Time Solvable Graph Class for the Minimum Biclique Edge Cover Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1202
EP - 1205
AU - Hideaki OTSUKI
PY - 2020
DO - 10.1587/transfun.2019DMP0004
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E103-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2020
AB - The minimum biclique edge cover problem (MBECP) is NP-hard for general graphs. It is known that if we restrict an input graph to the bipartite domino-free class, MBECP can be solved within polynomial-time of input graph size. We show a new polynomial-time solvable graph class for MBECP that is characterized by three forbidden graphs, a domino, a gem and K4. This graph class allows that an input graph is non-bipartite, and includes the bipartite domino-free graph class properly.
ER -
English
