Yixin Cao

activity

20102026

most citedOn Feedback Vertex Set: New Measure and New Structures

31 citations · 126 across the 26 of their papers we have counts for

collaborators

Showing 2017Show all

3 papers · 1 filter

cs.DS2017★ 18 cited

An $O^{*} (1.8 4^{k})$ Parameterized Algorithm for the Multiterminal Cut Problem

Yixin Cao, Jianer Chen, Jia-Hao Fan

We study the \emph{multiterminal cut} problem, which, given an $n$ -vertex graph whose edges are integer-weighted and a set of terminals, asks for a partition of the vertex set such…

cs.DS2017★ 1 cited

Vertex Deletion Problems on Chordal Graphs

Yixin Cao, Yuping Ke, Yota Otachi +1

Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis an…

cs.DS2017★ 2 cited

A Naive Algorithm for Feedback Vertex Set

Yixin Cao

Given a graph on $n$ vertices and an integer $k$ , the feedback vertex set problem asks for the deletion of at most $k$ vertices to make the graph acyclic. We show that a greedy bra…

An O∗(1.84k) Parameterized Algorithm for the Multiterminal Cut Problem

Vertex Deletion Problems on Chordal Graphs

A Naive Algorithm for Feedback Vertex Set

An $O^{*} (1.8 4^{k})$ Parameterized Algorithm for the Multiterminal Cut Problem