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

Minimum Spanning Tree Problem with Label Selection Masalah Pokok Spanning Minimum dengan Pemilihan Label

Akio FUJIYOSHI, Masakazu SUZUKI

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Dalam makalah ini, kami mengkaji masalah pokok rentang minimum dengan pemilihan label, iaitu masalah mencari pokok rentang minimum graf berlabel bucu di mana berat setiap tepi mungkin berbeza-beza bergantung pada pemilihan label bucu pada kedua-dua berakhir. Masalahnya amat penting sebagai aplikasi untuk OCR matematik. Ia ditunjukkan bahawa masalahnya adalah NP-hard. Walau bagaimanapun, untuk aplikasi kepada OCR matematik, adalah memadai untuk menangani hanya graf dengan lebar pokok yang kecil. Dalam makalah ini, algoritma masa linear untuk graf siri-selari dibentangkan. Memandangkan masalah pokok rentang minimum dengan pemilihan label berkait rapat dengan masalah pokok rentang minimum umum, hubungannya dibincangkan.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E94-D No.2 pp.233-239
Tarikh penerbitan
2011/02/01
Diumumkan
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.E94.D.233
Jenis Manuskrip
Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
kategori

Pengarang

Kata kunci

Contents [show]