31 citations · 126 across the 26 of their papers we have counts for
4 papers · 1 filter
A -Vertex Kernel for Maximum Internal Spanning Tree
Wenjun Li, Jianxin Wang, Jianer Chen +1
We consider the parameterized version of the maximum internal spanning tree problem, which, given an -vertex graph and a parameter , asks for a spanning tree with at least $k…
Chordal Editing is Fixed-Parameter Tractable
Yixin Cao, Dániel Marx
Graph modification problems are typically asked as follows: is there a small set of operations that transforms a given graph to have a certain property. The most commonly considere…
Forbidden Induced Subgraphs of Normal Helly Circular-Arc Graphs: Characterization and Detection
Yixin Cao, Luciano N. Grippo, Martín D. Safe
A normal Helly circular-arc graph is the intersection graph of arcs on a circle of which no three or less arcs cover the whole circle. Lin, Soulignac, and Szwarcfiter [Discrete App…
Linear Recognition of Almost Interval Graphs
Yixin Cao
Let $\mbox{interval} + k v$, $\mbox{interval} + k e$, and $\mbox{interval} - k e$ denote the classes of graphs that can be obtained from some interval graph by adding vertices,…