QUELQUES PROBLEMES DE CHEMINS POUR LES HYPERGRAPHES ORIENTES

Les BF-graphes sont une classe particuliere d'hypergraphes orientes. Quelques applications diversifiees pour cette famille importante, comme les bases de donnees et l'intelligence artificielle, sont deja connues. Il peut arriver qu'ils puissent aussi decrire le comportement des systemes concurrents. Les chercheurs presentent ici l'approche theorique de quelques problemes de cheminement pour les BF-graphes, surtout les BF-graphes acycliques. Apres les concepts fondamentaux d'hypergraphes orientes, ils presentent l'algorithme pour la determination d'un BF-chemin de complexite de O ; ils discutent aussi le probleme de la couverture par des chemins et, enfin, ils presentent une solution polynomiale pour un cas particulier de deux problemes de chemins avec contraintes, dans un BF-graphe acyclique. (A).

  • Authors:
    • MARKENSON, L
    • NGUYEN, S
  • Publication Date: 1991-4

Language

  • French

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01248278
  • Record Type: Publication
  • Source Agency: Institut Francais des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)
  • Files: ITRD
  • Created Date: Nov 20 2010 4:37AM