Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

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: Analisis Algoritma Graf bagi Rangkaian Blockchain Jenis DAG

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

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

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.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E106-D No.3 pp.272-283
Tarikh penerbitan
2023/03/01
Diumumkan
2022/12/22
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.2022FCP0007
Jenis Manuskrip
Special Section PAPER (Special Section on Foundations of Computer Science — Foundations of Computer Science Supporting the Information Society —)
kategori

Pengarang

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

Kata kunci

Contents [show]