Decomposing a Graph into Shortest Paths with Bounded Eccentricity

Etienne Birmelé 1 Fabien De Montgolfier 2, 3 Léo Planche 1, 3, 2 Laurent Viennot 2, 3, 4
1 MAP5 - UMR 8145 - Mathématiques Appliquées à Paris 5
2 GANG - Networks, Graphs and Algorithms
IRIF - Institut de Recherche en Informatique Fondamentale, Inria de Paris
3 IRIF - Institut de Recherche en Informatique Fondamentale
4 LINCS - Laboratory of Information, Network and Communication Sciences
Abstract : We introduce the problem of hub-laminar decomposition which generalizes that of computing a shortest path with minimum eccentricity (MESP). Intuitively, it consists in decomposing a graph into several paths that collectively have small eccentricity and meet only near their extremities. The problem is related to computing an isometric cycle with minimum eccentricity (MEIC). It is also linked to DNA reconstitution in the context of metagenomics in biology. We show that a graph having such a decomposition with long enough paths can be decomposed in polynomial time with approximated guaranties on the parameters of the decomposition. Moreover, such a decomposition with few paths allows to compute a compact representation of distances with additive distortion. We also show that having an isometric cycle with small eccentricity is related to the possibility of embedding the graph in a cycle with low distortion.
Keywords : Graph Decomposition Graph Clustering Distance Labeling MESP BFS
Type de document :
Communication dans un congrès
28th International Symposium on Algorithms and Computation (ISAAC 2017), Dec 2017, Phuket, Thailand. 〈10.4230/LIPIcs.ISAAC.2017.15〉
Liste complète des métadonnées
https://hal.inria.fr/hal-01671718
Contributeur : Fabien De Montgolfier <>
Soumis le : vendredi 22 décembre 2017 - 15:12:49
Dernière modification le : vendredi 16 novembre 2018 - 02:19:55

Identifiants

Collections

UPMC | MAP5 | INRIA | USPC | INRIA2017 | INRIA-ROCQ | UNIV-PARIS5 | SORBONNE-UNIVERSITE

Citation

Etienne Birmelé, Fabien De Montgolfier, Léo Planche, Laurent Viennot. Decomposing a Graph into Shortest Paths with Bounded Eccentricity. 28th International Symposium on Algorithms and Computation (ISAAC 2017), Dec 2017, Phuket, Thailand. 〈10.4230/LIPIcs.ISAAC.2017.15〉. 〈hal-01671718〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

181

Contact


archive-ouverte@inria.fr