-
The Treewidth of Java Programs
Intuitively, the treewidth of a graph $G$ measures how close $G$ is to being a tree. The lower the treewidth, the faster we can solve various optimization problems on... -
Fractional Coloring of Bounded Degree Trees
We study the dipath-coloring problem in bounded degree and treewidth symmetric digraphs, in which one needs to color the dipaths with a minimum number of colors, in... -
Java Programs do not have Bounded Treewidth
We show that the control-flow graphs of Java programs, due to the labelled break and continue statements, have no upper bound on their treewidth. A single Java method... -
Parameterized complexity of finding small degree-constrained subgraphs
International audience -
Parameterized Complexity of Connected Even/Odd Subgraph Problems
International audience -
On the treewidth and related parameters of random geometric graphs
International audience -
Linear min-max relation between the treewidth of H-minor-free graphs and its ...
International audience -
Lower Bounds on the Complexity of MSO_1 Model-Checking
International audience -
On treewidth approximations
We introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of... -
Approximating the treewidth of AT-free graphs
Using the specific structure of AT-free graphs, we give a 2-approximation algorithm for their treewidth. -
Chordal embeddings of planar graphs
Robertson and Seymour conjectured that the treewidth of a planar graph and the treewidth of its geometric dual differ by at most one. Lapoire solved this conjecture in... -
Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In
We show that for a graph $G$ on $n$ vertices its treewidth can be computed in $\mathcal{O}(poly(n) 1.9601^n)$ time. Our result is based on combinatorial upper bounds... -
Bidimensional Structures: Algorithms, Combinatorics and Logic (Dagstuhl Semin...
International audience -
Optimizing the Graph Minors Weak Structure Theorem
International audience -
Graphs and hypergraphs : algorithmic and algebraic complexities
Beware, this abstract comports irony and humor. In this dissertation, we defend the idea that, for any reasonnable model of computation, this is not the model that is... -
A note on domino treewidth
International audience
