La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Linear-Time Algorithm for Five-Partitioning Five-Connected Internally Triangulated Plane Graphs Un algorithme de temps linéaire pour les graphiques plans triangulés internes à cinq partitions et cinq connexions

Sayaka NAGAI, Shin-ichi NAKANO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Étant donné un graphique G=(V,E), cinq sommets distincts u1,u2,u3,u4,u5 V et cinq nombres naturels n1,n2,n3,n4,n5 tel que Σ5in = 1ni=|V|, nous souhaitons trouver une partition V1,V2,V3,V4,V5 de l'ensemble des sommets V tel que ui Vi|Vi|=ni et à la Vi induit un sous-graphe connecté de G pour chaque i1i5. Dans cet article, nous donnons un algorithme simple en temps linéaire pour trouver une telle partition si G est un graphe plan triangulé interne à 5 connexions et u1,u2,u3,u4,u5 sont situés sur la face extérieure de G. Notre algorithme est basé sur une « décomposition 5-canonique » de G, qui est une généralisation d'un st-une numérotation et un "ordonnancement canonique" connus dans le domaine des dessins graphiques.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.9 pp.2330-2337
Date de publication
2001/09/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Algorithmes et Structures de Données

Auteurs

Mots-clés

Table des matières