Path Separability of Graphs
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | DIOT, Emilie | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Institut universitaire de France [IUF] | |
| dc.contributor.author | GAVOILLE, Cyril | |
| dc.date.accessioned | 2024-04-15T09:49:11Z | |
| dc.date.available | 2024-04-15T09:49:11Z | |
| dc.date.created | 2010-08 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198236 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.subject.en | shortest path | |
| dc.subject.en | separator | |
| dc.subject.en | graph minor theory | |
| dc.subject.en | graph algorithms | |
| dc.title.en | Path Separability of Graphs | |
| dc.type | Document de travail - Pré-publication | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| dc.subject.hal | Informatique [cs]/Mathématique discrète [cs.DM] | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| hal.identifier | hal-00507833 | |
| hal.version | 1 | |
| hal.audience | Non spécifiée | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00507833v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=DIOT,%20Emilie&GAVOILLE,%20Cyril&rft.genre=preprint |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||