WEKO3
アイテム
DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks
http://hdl.handle.net/10061/0002000091
http://hdl.handle.net/10061/0002000091fda897f0-9c2c-4574-b6f2-9a6316bac310
| アイテムタイプ | 学術雑誌論文 / Journal Article(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-12-28 | |||||||||||
| タイトル | ||||||||||||
| タイトル | DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks | |||||||||||
| 言語 | ||||||||||||
| 言語 | eng | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | graph algorithm | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | computational complexity | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | directed acyclic graph | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | pathwidth | |||||||||||
| キーワード | ||||||||||||
| 主題Scheme | Other | |||||||||||
| 主題 | blockchain | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ | journal article | |||||||||||
| アクセス権 | ||||||||||||
| アクセス権 | open access | |||||||||||
| 著者 |
笠原, 正治
× 笠原, 正治× KAWAHARA,Jun
× MINATO,Shin-ichi
× MORI,Jumpei
|
|||||||||||
| 抄録 | ||||||||||||
| 内容記述タイプ | 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. | |||||||||||
| 書誌情報 |
en : IEICE Transactions on Information and Systems 巻 E106.D, 号 3, p. 272-283, 発行日 2023-03-01 |
|||||||||||
| 出版者 | ||||||||||||
| 出版者 | Institute of Electronics, Information and Communication Engineers | |||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||
| 収録物識別子 | 1745-1361 | |||||||||||
| 出版者版DOI | ||||||||||||
| 関連タイプ | isReplacedBy | |||||||||||
| 識別子タイプ | DOI | |||||||||||
| 関連識別子 | https://doi.org/10.1587/transinf.2022FCP0007 | |||||||||||
| 出版者版URI | ||||||||||||
| 関連タイプ | isReplacedBy | |||||||||||
| 識別子タイプ | URI | |||||||||||
| 関連識別子 | https://www.jstage.jst.go.jp/article/transinf/E106.D/3/E106.D_2022FCP0007/_article | |||||||||||
| 権利 | ||||||||||||
| 権利情報 | c 2023 The Institute of Electronics, Information and Communication Engineers | |||||||||||
| 著者版フラグ | ||||||||||||
| 出版タイプ | NA | |||||||||||
