A general scheme for deciding the branchwidth
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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...