On the Path Separability of Planar 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] | |
| dc.contributor.author | GAVOILLE, Cyril | |
| dc.date.accessioned | 2024-04-15T09:50:50Z | |
| dc.date.available | 2024-04-15T09:50:50Z | |
| dc.date.created | 2009-03-13 | |
| dc.date.issued | 2009-09 | |
| dc.date.conference | 2009-09-07 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198379 | |
| dc.description.abstractEn | It is known that every weighted planar graph with n vertices contains three shortest paths whose removal halves the graph into connected components of at most n/2 vertices. It is open whether this property remains true with the use of two shortest paths only. We show that two shortest paths are enough for a large family of planar graphs, called face-separable, composed of graphs for which every induced subgraph can be halved by removing the border of a face in some suitable embedding of the subgraph. We also show that this non-trivial family of graphs includes unbounded treewidth graphs. | |
| dc.language.iso | en | |
| dc.source.title | EuroComb 2009 | |
| dc.subject.en | treewidth | |
| dc.subject.en | planar graphs | |
| dc.subject.en | path-separable | |
| dc.title.en | On the Path Separability of Planar Graphs | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1016/j.endm.2009.07.091 | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| bordeaux.page | 549-552 | |
| bordeaux.volume | 34C | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | EuroComb 2009, Bordeaux, France | |
| bordeaux.country | FR | |
| bordeaux.title.proceeding | EuroComb 2009 | |
| bordeaux.conference.city | Bordeaux | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00408228 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2009-09-11 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00408228v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=EuroComb%202009&rft.date=2009-09&rft.volume=34C&rft.spage=549-552&rft.epage=549-552&rft.au=DIOT,%20Emilie&GAVOILLE,%20Cyril&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||