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

DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks DAG-Pathwidth : analyses algorithmiques graphiques des réseaux blockchain de type DAG

Shoji KASAHARA, Jun KAWAHARA, Shin-ichi MINATO, Jumpei MORI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Cet article analyse un réseau blockchain formant un graphe acyclique dirigé (DAG), appelé blockchain de type DAG, du point de vue de la théorie des algorithmes de graphes. Pour utiliser une blockchain de type DAG, des problèmes d’optimisation de graphes NP-hard sur le DAG doivent être résolus. Bien que divers problèmes liés aux graphes non orientés et orientés puissent être résolus efficacement en utilisant les notions de paramètres de graphes, ces paramètres actuellement connus n'ont aucun sens pour les DAG, ce qui implique qu'il est sans espoir de concevoir des algorithmes efficaces basés sur les paramètres de tels problèmes. Dans ce travail, nous proposons un nouveau paramètre de graphe pour les graphes orientés appelé DAG-pathwidth, qui représente la proximité d'un chemin dirigé. Il s'agit d'une extension de la largeur de chemin, un paramètre de graphe bien connu pour les graphes non orientés. Nous analysons les caractéristiques de la largeur de chemin DAG et prouvons que le calcul de la largeur de chemin DAG d'un DAG (graphe orienté en général) est NP-complet. Enfin, nous proposons un algorithme efficace pour une variante du maximum k-problème d'ensemble indépendant pour la blockchain de type DAG lorsque la largeur du chemin DAG du graphe d'entrée est petite.

Publication
IEICE TRANSACTIONS on Information Vol.E106-D No.3 pp.272-283
Date de publication
2023/03/01
Publicisé
2022/12/22
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2022FCP0007
Type de manuscrit
Special Section PAPER (Special Section on Foundations of Computer Science — Foundations of Computer Science Supporting the Information Society —)
Catégories

Auteurs

Shoji KASAHARA
  Nara Institute of Science and Technology
Jun KAWAHARA
  Kyoto University
Shin-ichi MINATO
  Kyoto University
Jumpei MORI
  Kyoto University

Mots-clés

Table des matières