23 citations · 76 across the 30 of their papers we have counts for
26 papers · 1 filter
On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
Svein Høgemo, Benjamin Bergougnoux, Ulrik Brandes +2
The minimum height of vertex and edge partition trees are well-studied graph parameters known as, for instance, vertex and edge ranking number. While they are NP-hard to determine…
A linear fixed parameter tractable algorithm for connected pathwidth
Mamadou Moustapha Kanté, Christophe Paul, Dimitrios M. Thilikos
The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search wh…
A polynomial time algorithm to compute the connected tree-width of a series-parallel graph
Guillaume Mescoff, Christophe Paul, Dimitrios Thilikos
It is well known that the treewidth of a graph corresponds to the node search number where a team of cops is pursuing a robber that is lazy, visible and has the ability to move…
Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
Florian Barbero, Christophe Paul, Michał Pilipczuk
A simple digraph is semi-complete if for any two of its vertices and , at least one of the arcs and is present. We study the complexity of computing two layo…
Parameterized complexity of finding a spanning tree with minimum reload cost diameter
Julien Baste, Didem Gözüpek, Christophe Paul +3
We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirect…
Explicit linear kernels for packing problems
Valentin Garnero, Christophe Paul, Ignasi Sau +1
During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence…