The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs

Autor: Diot, Emilie, Radovanović, Marko, Trotignon, Nicolas, Vušković, Kristina

Publikováno v: Journal of Combinatorial Theory, Series B, Volume 143, 2020, Pages 123-147

Truemper configurations are four types of graphs (namely thetas, wheels, prisms and pyramids) that play an important role in the proof of several decomposition theorems for hereditary graph classes. In this paper, we prove two structure theorems: one

Externí odkaz: http://arxiv.org/abs/1504.01862

Detecting wheels

Autor: Diot, Emilie, Tavenas, Sébastien, Trotignon, Nicolas

Publikováno v: Applicable Analysis and Discrete Mathematics, 8:111-122, 2014

A \emph{wheel} is a graph made of a cycle of length at least~4 together with a vertex that has at least three neighbors in the cycle. We prove that the problem whose instance is a graph $G$ and whose question is "does $G$ contains a wheel as an induc

Externí odkaz: http://arxiv.org/abs/1308.6433

Sur la difficulté de séparer un graphe par des plus courts chemins

Autor: Diot, Emilie, Gavoille, Cyril, Ochem, Pascal

Publikováno v: 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel)
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2011, Cap Estérel, France

International audience; Les schémas de routage et de calcul de distances les plus efficaces sont conçus à partir de décompositions hiérarchiques de la topologie en plus courts chemins. Ces constructions sont calculables efficacement pour de nomb

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::18cd1f205fe0335dc93c45ee4cb978bd
https://hal.inria.fr/inria-00588312

Path Separability of Graphs.

Autor: Diot, Emilie, Gavoille, Cyril

Publikováno v: Frontiers in Algorithmics (9783642145520); 2010, p262-273, 12p