Feedback vertex set on chordal bipartite graphs
Kloks, Ton ; Liu, Ching-Hao ; Poon, Sheung-Hung
arXiv, 1104.3915 / Harvested from arXiv
Text on arXiv
Let G=(A,B,E) be a bipartite graph with color classes A and B. The graph G is chordal bipartite if G has no induced cycle of length more than four. Let G=(V,E) be a graph. A feedback vertex set F is a set of vertices F subset V such that G-F is a forest. The feedback vertex set problem asks for a feedback vertex set of minimal cardinality. We show that the feedback vertex set problem can be solved in polynomial time on chordal bipartite graphs.
Publié le : 2011-04-19
Classification:  Mathematics - Combinatorics 
@article{1104.3915,
     author = {Kloks, Ton and Liu, Ching-Hao and Poon, Sheung-Hung},
     title = {Feedback vertex set on chordal bipartite graphs},
     journal = {arXiv},
     volume = {2011},
     number = {0},
     year = {2011},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1104.3915}
}

Kloks, Ton; Liu, Ching-Hao; Poon, Sheung-Hung. Feedback vertex set on chordal bipartite graphs. arXiv, Tome 2011 (2011) no. 0, . http://gdmltest.u-ga.fr/item/1104.3915/