Path Separability of Graphs
DIOT, Emilie
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Institut universitaire de France [IUF]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Institut universitaire de France [IUF]
DIOT, Emilie
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Institut universitaire de France [IUF]
< Réduire
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Institut universitaire de France [IUF]
Langue
en
Document de travail - Pré-publication
Résumé en anglais
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, ...Lire la suite >
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.< Réduire
Mots clés en anglais
shortest path
separator
graph minor theory
graph algorithms
Origine
Importé de halUnités de recherche