-
Pathwidth of outerplanar graphs
We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin, after... -
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... -
Experimental Evaluation of a Branch and Bound Algorithm for computing Pathwidth
It is well known that many NP-hard problems are tractable in the class of bounded pathwidth graphs. In particular, path-decompositions of graphs are an important... -
Classes of graphs with restricted interval models
International audience -
A new two-variable generalization of the chromatic polynomial
International audience -
Exclusive Graph Searching vs. Pathwidth
In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a...
