A general scheme for deciding the branchwidth - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2004

A general scheme for deciding the branchwidth

(1)
1

Résumé

We adapt some decision theorems about treewidth to the branchwidth and use this theorems to prove that the branchwidth of circular-arc graphs can be computed in polynomial time.
Nous adaptons des résultats de décision sur les décompositions arborescentes aux décompositions en branches. Nous utilisons ensuite ces résultats pour montrer que le calcul de la largeur de branches des graphes d’intervalles circulaires peut se faire en temps polynomial
Fichier principal
Vignette du fichier
RR2004-34.pdf (242.07 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102054 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102054 , version 1

Citer

Frédéric Mazoit. A general scheme for deciding the branchwidth. [Research Report] LIP RR-2004-34, Laboratoire de l'informatique du parallélisme. 2004, 2+11p. ⟨hal-02102054⟩
4 Consultations
11 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More