pith. sign in

arxiv: 1104.3915 · v2 · pith:WERRP6CTnew · submitted 2011-04-20 · 🧮 math.CO

Feedback vertex set on chordal bipartite graphs

Ton Kloks , Ching-Hao Liu , Sheung-Hung Poon This is my paper
classification 🧮 math.CO
keywords feedbackvertexbipartitechordalgraphgraphsproblemasks
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Sparse induced subgraphs in $P_7$-free graphs of bounded clique number

    cs.DS 2024-12 unverdicted novelty 6.0

    Polynomial-time algorithms exist for all CMSO2-expressible sparse induced subgraph problems in P7-free graphs of bounded clique number.