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
Este artigo analisa uma rede blockchain formando um grafo acíclico direcionado (DAG), denominado blockchain do tipo DAG, do ponto de vista da teoria do algoritmo de grafos. Para usar um blockchain do tipo DAG, é necessário resolver problemas de otimização de gráficos NP-hard no DAG. Embora vários problemas para grafos direcionados e não direcionados possam ser eficientemente resolvidos usando as noções de parâmetros de grafos, esses parâmetros atualmente conhecidos não têm sentido para DAGs, o que implica que é inútil projetar algoritmos eficientes baseados nos parâmetros para tais problemas. Neste trabalho, propomos um novo parâmetro gráfico para grafos direcionados denominado DAG-pathwidth, que representa a proximidade de um caminho direcionado. Esta é uma extensão da largura de caminho, um parâmetro gráfico bem conhecido para gráficos não direcionados. Analisamos as características da largura de caminho do DAG e provamos que o cálculo da largura de caminho do DAG de um DAG (gráfico direcionado em geral) é NP-completo. Finalmente, propomos um algoritmo eficiente para uma variante do máximo k-problema de conjunto independente para o blockchain do tipo DAG quando a largura do caminho DAG do gráfico de entrada é pequena.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -