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

The Huffman Tree Problem with Upper-Bounded Linear Functions Masalah Pokok Huffman dengan Fungsi Linear Sempadan Atas

Hiroshi FUJIWARA, Yuichi SHIRAI, Hiroaki YAMAMOTO

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Pembinaan kod Huffman boleh difahami sebagai masalah mencari pokok binari penuh supaya setiap daun dikaitkan dengan fungsi linear kedalaman daun dan jumlah nilai fungsi diminimumkan. Fujiwara dan Jacobs memanjangkan ini kepada fungsi umum dan membuktikan masalah lanjutan adalah NP-hard. Penulis juga menunjukkan kes di mana fungsi yang berkaitan dengan daun adalah setiap satu tidak berkurangan dan cembung boleh diselesaikan dalam masa polinomial. Walau bagaimanapun, kerumitan kes fungsi bukan cembung tidak berkurangan masih tidak diketahui. Dalam makalah ini kami cuba mendedahkan kerumitan dengan mempertimbangkan fungsi bukan cembung tidak menurun yang setiap satunya mengambil nilai yang lebih kecil sama ada fungsi linear atau pemalar. Akibatnya, kami menyediakan algoritma masa polinomial untuk dua subkelas fungsi tersebut.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.474-480
Tarikh penerbitan
2022/03/01
Diumumkan
2021/10/12
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.2021FCP0006
Jenis Manuskrip
Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
kategori

Pengarang

Hiroshi FUJIWARA
  Shinshu University
Yuichi SHIRAI
  Shinshu University
Hiroaki YAMAMOTO
  Shinshu University

Kata kunci

Contents [show]