Title :
On Minimum Feedback Vertex Sets in Graphs
Author :
Takaoka, Asahi ; Tayu, Satoshi ; Ueno, Satoshi
Author_Institution :
Dept. of Commun. & Integrated Syst., Tokyo Inst. of Technol., Tokyo, Japan
Abstract :
For the minimum feedback vertex set problem, we show a linear time algorithm for bipartite permutation graphs, the NP-hardness for grid intersection graphs, and a polynomial time algorithm for graphs with maximum degree at most three.
Keywords :
computational complexity; graph theory; NP-hardness; bipartite permutation graphs; grid intersection graphs; linear time algorithm; minimum feedback vertex sets; polynomial time algorithm; Bipartite graph; Bismuth; Dynamic programming; Heuristic algorithms; Indexes; Polynomials; bipartite permutation graph; feedback vertex set; graph with maximum degree at most three; grid intersection graph; matroid parity problem; maximum-genus connected vertex cover;
Conference_Titel :
Networking and Computing (ICNC), 2012 Third International Conference on
Conference_Location :
Okinawa
Print_ISBN :
978-1-4673-4624-5
DOI :
10.1109/ICNC.2012.81
