DISSAUX , Thomas

Graph decompositions are a powerful tool aimed to divide a graph into several parts, called bags, connected in a tree-like or a path-like fashion, depending on whether we consider a tree-decomposition or a path-decomposition. They can be used to solve some NP-hard problems in linear time, as long as the maximum size of the bags (i.e. the width)...

A path-decomposition of a graph G = (V, E) is a sequence of subsets of V , called bags, that satisfy some connectivity properties. The length of a path-decomposition of a graph G is the greatest distance between two vertices that belong to a same bag and the pathlength, denoted by pl(G), of G is the smallest length of its path-decompositions....

Une décomposition linéaire (path-decomposition) d'un graphe G = (V, E) est une représentation de G comme une séquence de sous-ensembles (appelés sacs) de V vérifiant des propriétés de connexité. La longueur d'une décomposition linéaire est le plus grand diamètre d'un de ses sacs et la longueur linéaire de G est la plus petite longueur d'une de...

A path-decomposition of a graph G = (V, E) is a sequence of subsets of V , called bags, that satisfy some connectivity properties. The length of a path-decomposition of a graph G is the greatest distance between two vertices that belong to a same bag and the pathlength, denoted by p (G), of G is the smallest length of its path-decompositions....

La longueur d'une décomposition arborescente d'un graphe G est la plus grande distance entre deux sommets d'un sac de la décomposition. La longueur arborescente de G est la plus petite longueur d'une de ses décompositions arborescentes. Ce paramètre aétéétudié pour ses applications algorithmiques dans des problèmes classiques comme le problème...

The length of a tree-decomposition of a graph is the maximum distance (in the graph) between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decompositions. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling...

The Hunters and Rabbit game is played on a graph G where the Hunter player shoots at k vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if it can ensure that its position is never shot. The Hunter player wins otherwise....

The Hunters and Rabbit game is played on a graph G where the Hunter player shoots at k vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if he can ensure that its position is never shot. The Hunter player wins otherwise....

The length of a tree-decomposition of a graph is the maximum distance between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decomposition. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or...

The length of a tree-decompositionof a graph is the maximum distance between two vertices of a same bag of the decomposition. The treelength of a graph is the minimum length among its tree-decomposition. Treelength of graphs has been studied for its algorithmic applications in classical metric problems such as Traveling Salesman Problem or...

The Hunters and Rabbit game is played on a graph G where the Hunter player shoots at k vertices in every round while the Rabbit player occupies an unknown vertex and, if it is not shot, must move to a neighbouring vertex after each round. The Rabbit player wins if he can ensure that its position is never shot. The Hunter player wins otherwise....