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

Algorithms for Generating Maximum Weight Independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs Algorithmes pour générer des ensembles indépendants de poids maximum dans des graphiques circulaires, des graphiques de chevauchement d'arc circulaire et des graphiques en araignée

Masakuni TAKI, Hirotaka HATAKENAKA, Toshinobu KASHIWABARA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans cet article, nous proposons un algorithme pour générer des ensembles indépendants de poids maximum dans un graphe circulaire, c'est-à-dire pour afficher tous les ensembles indépendants de poids maximum un par un sans duplication. La complexité temporelle est O(n3 + β ), où n est le nombre de sommets, la taille de sortie β, c'est-à-dire la somme des cardinalités des ensembles de sortie. Il est montré que la même approche peut être appliquée aux graphes en araignée et aux graphes de chevauchement en arc de cercle.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.8 pp.1636-1640
Date de publication
1999/08/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Graphiques et réseaux

Auteurs

Mots-clés

Table des matières