Feedback vertex set on chordal bipartite graphs

Details Feedback vertex set on chordal bipartite graphs Feedback vertex set on chordal bipartite graphs

2011-04-20

arxiv.org/abs/1104.3915v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Feedback vertex set on chordal bipartite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Feedback vertex set on chordal bipartite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Feedback vertex set on chordal bipartite graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-431761