Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Path Separability of Graphs

Emilie Diot 1, 2 Cyril Gavoille 1, 2, 3
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
CNRS - Centre National de la Recherche Scientifique : UMR5800, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Inria Bordeaux - Sud-Ouest, Université Sciences et Technologies - Bordeaux 1
Abstract : In this paper we investigate the structural properties of $k$-path separable graphs, that are the graphs that can be separated by a set of $k$ shortest paths. We identify several graph families having such path separability, and we show that this property is closed under minor taking. In particular we establish a list of forbidden minors for $1$-path separable graphs.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00507833
Contributor : Cyril Gavoille <>
Submitted on : Wednesday, September 22, 2010 - 7:01:19 PM
Last modification on : Tuesday, February 9, 2021 - 3:00:04 PM
Long-term archiving on: : Thursday, December 1, 2016 - 10:08:11 PM

File

a.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00507833, version 3

Collections

Citation

Emilie Diot, Cyril Gavoille. Path Separability of Graphs. 2010. ⟨hal-00507833v3⟩

Share

Metrics

Record views

371

Files downloads

457