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
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.
Shoji KASAHARA
Nara Institute of Science and Technology
Jun KAWAHARA
Kyoto University
Shin-ichi MINATO
Kyoto University
Jumpei MORI
Kyoto University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Shoji KASAHARA, Jun KAWAHARA, Shin-ichi MINATO, Jumpei MORI, "DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 3, pp. 272-283, March 2023, doi: 10.1587/transinf.2022FCP0007.
Abstract: This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022FCP0007/_p
Copier
@ARTICLE{e106-d_3_272,
author={Shoji KASAHARA, Jun KAWAHARA, Shin-ichi MINATO, Jumpei MORI, },
journal={IEICE TRANSACTIONS on Information},
title={DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks},
year={2023},
volume={E106-D},
number={3},
pages={272-283},
abstract={This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.},
keywords={},
doi={10.1587/transinf.2022FCP0007},
ISSN={1745-1361},
month={March},}
Copier
TY - JOUR
TI - DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks
T2 - IEICE TRANSACTIONS on Information
SP - 272
EP - 283
AU - Shoji KASAHARA
AU - Jun KAWAHARA
AU - Shin-ichi MINATO
AU - Jumpei MORI
PY - 2023
DO - 10.1587/transinf.2022FCP0007
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2023
AB - This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the viewpoint of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.
ER -