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

What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? --Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples-- Quelles caractéristiques structurelles créent des problèmes de graphes pour avoir des algorithmes parallèles efficaces ? --Utilisation de graphiques planaires extérieurs, de graphiques trapézoïdaux et de graphiques en tournoi comme exemples--

Shigeru MASUYAMA, Shin-ichi NAKAYAMA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Cet article analyse quelles caractéristiques structurelles des problèmes de graphes permettent des algorithmes parallèles efficaces. Nous étudions quelques algorithmes parallèles pour des problèmes typiques sur trois types de graphiques, les graphiques planaires externes, les graphiques trapézoïdaux et les graphiques en tournoi. Nos résultats sur le problème du chemin le plus court, le problème du chemin le plus long et le problème du flux maximum sur les graphes planaires externes, le problème de l'ensemble dominant connecté de poids minimum et le problème de coloration sur les graphes trapézoïdaux et le problème du chemin hamiltonien et du cycle hamiltonien sur les graphes en tournoi sont adoptés. comme exemples concrets.

Publication
IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.541-549
Date de publication
2000/03/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
INVITED SURVEY PAPER
Catégories
Algorithmes parallèles et distribués

Auteurs

Mots-clés

Table des matières