23 citations · 76 across the 30 of their papers we have counts for
6 papers · 1 filter
Hitting and Harvesting Pumpkins
Gwenaël Joret, Christophe Paul, Ignasi Sau +2
The "c-pumpkin" is the graph with two vertices linked by c>0 parallel edges. A c-pumpkin-model in a graph G is a pair A,B of disjoint subsets of vertices of G, each inducing a conn…
Contracting Graphs to Paths and Trees
Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque +2
Vertex deletion and edge deletion problems play a central role in Parameterized Complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and…
Practical and Efficient Circle Graph Recognition
Emeric Gioan, Christophe Paul, Marc Tedder +1
Circle graphs are the intersection graphs of chords in a circle. This paper presents the first sub-quadratic recognition algorithm for the class of circle graphs. Our algorithm is…
Practical and Efficient Split Decomposition via Graph-Labelled Trees
Emeric Gioan, Christophe Paul, Marc Tedder +1
Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigat…
Obtaining a Bipartite Graph by Contracting Few Edges
Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov +1
We initiate the study of the Bipartite Contraction problem from the perspective of parameterized complexity. In this problem we are given a graph and an integer , and the ta…
Conflict Packing: an unifying technique to obtain polynomial kernels for editing problems on dense instances
Christophe Paul, Anthony Perez, Stéphan Thomassé
We develop a technique that we call Conflict Packing in the context of kernelization, obtaining (and improving) several polynomial kernels for editing problems on dense instances.…