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 Parallel Algorithm for Finding All Hinge Vertices of a Trapezoid Graph Un algorithme parallèle pour trouver tous les sommets charnières d'un graphe trapézoïdal

Hirotoshi HONMA, Shigeru MASUYAMA

  • Vues en texte intégral

    0

  • Citer

Résumé:

S'il existe deux sommets dans G dont la distance s'allonge lorsqu'un sommet u est supprimé, alors u est défini comme un sommet charnière. Trouver l'ensemble des sommets charnières dans un graphique est utile pour identifier les nœuds critiques dans un réseau réel. Un certain nombre d'études concernant les sommets charnières ont été réalisées ces dernières années. Dans un certain nombre de problèmes de graphes, il est connu que des algorithmes séquentiels ou parallèles plus efficaces peuvent être développés en limitant les classes de graphes. Dans cet article, nous proposerons un algorithme parallèle qui s'exécute dans O(Journal n) temps avec O(n) processeurs sur CREW PRAM pour trouver tous les sommets charnières d'un graphique trapézoïdal.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.1031-1040
Date de publication
2002/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