A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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: análises algorítmicas gráficas de redes Blockchain do tipo DAG

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

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Information Vol.E106-D No.3 pp.272-283
Data de publicação
2023/03/01
Publicitada
2022/12/22
ISSN online
1745-1361
DOI
10.1587/transinf.2022FCP0007
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science — Foundations of Computer Science Supporting the Information Society —)
Categoria

autores

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

Palavra-chave