Mostrar el registro sencillo del ítem

On the Path Separability of Planar Graphs

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorDIOT, Emilie
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorGAVOILLE, Cyril
dc.date.accessioned2024-04-15T09:50:50Z
dc.date.available2024-04-15T09:50:50Z
dc.date.created2009-03-13
dc.date.issued2009-09
dc.date.conference2009-09-07
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198379
dc.description.abstractEnIt 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.isoen
dc.source.titleEuroComb 2009
dc.subject.entreewidth
dc.subject.enplanar graphs
dc.subject.enpath-separable
dc.title.enOn the Path Separability of Planar Graphs
dc.typeCommunication dans un congrès
dc.identifier.doi10.1016/j.endm.2009.07.091
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.page549-552
bordeaux.volume34C
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleEuroComb 2009, Bordeaux, France
bordeaux.countryFR
bordeaux.title.proceedingEuroComb 2009
bordeaux.conference.cityBordeaux
bordeaux.peerReviewedoui
hal.identifierhal-00408228
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2009-09-11
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00408228v1
bordeaux.COinSctx_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


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem