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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Akio FUJIYOSHI, Masakazu SUZUKI, "Minimum Spanning Tree Problem with Label Selection" in IEICE TRANSACTIONS on Information,
vol. E94-D, no. 2, pp. 233-239, February 2011, doi: 10.1587/transinf.E94.D.233.
Abstract: In this paper, we study the minimum spanning tree problem with label selection, that is, the problem of finding a minimum spanning tree of a vertex-labeled graph where the weight of each edge may vary depending on the selection of labels of vertices at both ends. The problem is especially important as the application to mathematical OCR. It is shown that the problem is NP-hard. However, for the application to mathematical OCR, it is sufficient to deal with only graphs with small tree-width. In this paper, a linear-time algorithm for series-parallel graphs is presented. Since the minimum spanning tree problem with label selection is closely related to the generalized minimum spanning tree problem, their relation is discussed.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.233/_p
Salinan
@ARTICLE{e94-d_2_233,
author={Akio FUJIYOSHI, Masakazu SUZUKI, },
journal={IEICE TRANSACTIONS on Information},
title={Minimum Spanning Tree Problem with Label Selection},
year={2011},
volume={E94-D},
number={2},
pages={233-239},
abstract={In this paper, we study the minimum spanning tree problem with label selection, that is, the problem of finding a minimum spanning tree of a vertex-labeled graph where the weight of each edge may vary depending on the selection of labels of vertices at both ends. The problem is especially important as the application to mathematical OCR. It is shown that the problem is NP-hard. However, for the application to mathematical OCR, it is sufficient to deal with only graphs with small tree-width. In this paper, a linear-time algorithm for series-parallel graphs is presented. Since the minimum spanning tree problem with label selection is closely related to the generalized minimum spanning tree problem, their relation is discussed.},
keywords={},
doi={10.1587/transinf.E94.D.233},
ISSN={1745-1361},
month={February},}
Salinan
TY - JOUR
TI - Minimum Spanning Tree Problem with Label Selection
T2 - IEICE TRANSACTIONS on Information
SP - 233
EP - 239
AU - Akio FUJIYOSHI
AU - Masakazu SUZUKI
PY - 2011
DO - 10.1587/transinf.E94.D.233
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2011
AB - In this paper, we study the minimum spanning tree problem with label selection, that is, the problem of finding a minimum spanning tree of a vertex-labeled graph where the weight of each edge may vary depending on the selection of labels of vertices at both ends. The problem is especially important as the application to mathematical OCR. It is shown that the problem is NP-hard. However, for the application to mathematical OCR, it is sufficient to deal with only graphs with small tree-width. In this paper, a linear-time algorithm for series-parallel graphs is presented. Since the minimum spanning tree problem with label selection is closely related to the generalized minimum spanning tree problem, their relation is discussed.
ER -