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 to Find Independent Spanning Trees in Maximal Planar Graphs Un algorithme de temps linéaire pour trouver des arbres couvrants indépendants dans des graphiques planaires maximaux

Sayaka NAGAI, Shin-ichi NAKANO

  • Vues en texte intégral

    1

  • Citer

Résumé:

Étant donné un graphique G, un sommet désigné r et un nombre naturel k, nous souhaitons trouver k arbres couvrants "indépendants" de G enraciné à r, Qui est, k s'étendant sur des arbres tels que, pour tout sommet v, k chemins reliant r et à la v dans le k les arbres sont intérieurement disjoints dans G. Dans cet article, nous donnons un algorithme en temps linéaire pour trouver k arbres couvrants indépendants dans un k-graphe planaire maximal connecté enraciné à n'importe quel sommet désigné.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1102-1109
Date de publication
2001/05/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Mots-clés

Table des matières