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 Faster and Flexible Algorithm for a Location Problem on Undirected Flow Networks Un algorithme plus rapide et flexible pour un problème de localisation sur des réseaux à flux non dirigés

Hiro ITO, Hideyuki UEHARA, Mitsuo YOKOYAMA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Pour un graphique donné G=(V, E), capacités de bord c(e) pour les bords e E, et les demandes de flux d(v) pour les nœuds v V, un problème de recherche de l'ensemble source de taille minimale S V tel que le débit maximum entre S et à la v est supérieur ou égal à d(v) pour chaque v V est appelé problème de couverture plurielle généralisée (GPC). Pour ce problème, O(np s(n,m)) un algorithme temporel est présenté, où n, m et p est le nombre de nœuds, d'arêtes et différentes valeurs de d(v), respectivement, et s(n,m) est le temps nécessaire pour résoudre le problème de flux maximum d'un graphe avec n nœuds et m bords. Cet algorithme construit également un ensemble de solutions optimales en même temps. Cette propriété est pratique pour l’appliquer à des problèmes réels, car d’autres contraintes peuvent également être prises en compte.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.704-712
Date de publication
2000/04/25
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