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

Graph Augmentation Problems with Degree-Unchangeable Vertices Problèmes d'augmentation de graphe avec des sommets à degré immuable

Toshiya MASHIMA, Toshimasa WATANABE

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le k-problème d'augmentation de connectivité des sommets pour un ensemble spécifié de sommets d'un graphe avec des sommets de degré immuable, kVCA(G,S,D), est défini comme suit : « Étant donné un entier positif k, un graphe non orienté G=(V,E), un ensemble spécifié de sommets S V et un ensemble de sommets à degrés variables D V, trouver le plus petit ensemble d'arêtes E de telle sorte que la connectivité des sommets de S dans (V,E E) Est au moins k et à la E {(u,v) u,v D}. " Le principal résultat de l'article est de vérifier l'existence d'une solution et de trouver une solution à 2VCA (G,S,D) ou 3VCA(G,S,D) peut être fait en O(|V|+|E|) ou O(|V|(|V|+|E|)) temps, respectivement.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.3 pp.781-793
Date de publication
2001/03/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
Catégories

Auteurs

Mots-clés

Table des matières