On Minimum Feedback Vertex Sets in Bipartite Graphs and Degree-Constraint Graphs
Summary :
We consider the minimum feedback vertex set problem for some bipartite graphs and degree-constrained graphs. We show that the problem is linear time solvable for bipartite permutation graphs and NP-hard for grid intersection graphs. We also show that the problem is solvable in O(n2log 6n) time for n-vertex graphs with maximum degree at most three.
- Publication
- IEICE TRANSACTIONS on Information Vol.E96-D No.11 pp.2327-2332
- Publication Date
- 2013/11/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E96.D.2327
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Asahi TAKAOKA
Tokyo Institute of Technology
Satoshi TAYU
Tokyo Institute of Technology
Shuichi UENO
Tokyo Institute of Technology
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
Asahi TAKAOKA, Satoshi TAYU, Shuichi UENO, "On Minimum Feedback Vertex Sets in Bipartite Graphs and Degree-Constraint Graphs" in IEICE TRANSACTIONS on Information,
vol. E96-D, no. 11, pp. 2327-2332, November 2013, doi: 10.1587/transinf.E96.D.2327.
Abstract: We consider the minimum feedback vertex set problem for some bipartite graphs and degree-constrained graphs. We show that the problem is linear time solvable for bipartite permutation graphs and NP-hard for grid intersection graphs. We also show that the problem is solvable in O(n2log 6n) time for n-vertex graphs with maximum degree at most three.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.2327/_p
Copy
@ARTICLE{e96-d_11_2327,
author={Asahi TAKAOKA, Satoshi TAYU, Shuichi UENO, },
journal={IEICE TRANSACTIONS on Information},
title={On Minimum Feedback Vertex Sets in Bipartite Graphs and Degree-Constraint Graphs},
year={2013},
volume={E96-D},
number={11},
pages={2327-2332},
abstract={We consider the minimum feedback vertex set problem for some bipartite graphs and degree-constrained graphs. We show that the problem is linear time solvable for bipartite permutation graphs and NP-hard for grid intersection graphs. We also show that the problem is solvable in O(n2log 6n) time for n-vertex graphs with maximum degree at most three.},
keywords={},
doi={10.1587/transinf.E96.D.2327},
ISSN={1745-1361},
month={November},}
Copy
TY - JOUR
TI - On Minimum Feedback Vertex Sets in Bipartite Graphs and Degree-Constraint Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 2327
EP - 2332
AU - Asahi TAKAOKA
AU - Satoshi TAYU
AU - Shuichi UENO
PY - 2013
DO - 10.1587/transinf.E96.D.2327
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2013
AB - We consider the minimum feedback vertex set problem for some bipartite graphs and degree-constrained graphs. We show that the problem is linear time solvable for bipartite permutation graphs and NP-hard for grid intersection graphs. We also show that the problem is solvable in O(n2log 6n) time for n-vertex graphs with maximum degree at most three.
ER -
English
