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
Makalah ini menganalisis rangkaian rantaian blok yang membentuk graf asiklik terarah (DAG), yang dipanggil rantaian jenis DAG, dari sudut pandangan teori algoritma graf. Untuk menggunakan rantaian blok jenis DAG, masalah pengoptimuman graf keras NP pada DAG diperlukan untuk diselesaikan. Walaupun pelbagai masalah untuk graf tidak terarah dan terarah boleh diselesaikan dengan cekap dengan menggunakan tanggapan parameter graf, parameter yang diketahui pada masa ini tidak bermakna untuk DAG, yang membayangkan bahawa tidak ada harapan untuk mereka bentuk algoritma yang cekap berdasarkan parameter untuk masalah tersebut. Dalam kerja ini, kami mencadangkan parameter graf baru untuk graf terarah yang dipanggil lebar laluan DAG, yang mewakili kedekatan dengan laluan terarah. Ini adalah lanjutan daripada lebar laluan, parameter graf yang terkenal untuk graf tidak terarah. Kami menganalisis ciri lebar laluan DAG dan membuktikan bahawa pengiraan lebar laluan DAG bagi DAG (graf terarah secara umum) ialah NP-lengkap. Akhir sekali, kami mencadangkan algoritma yang cekap untuk varian maksimum k-masalah set bebas untuk rantaian blok jenis DAG apabila lebar laluan DAG graf input adalah kecil.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -