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
본 논문에서는 레이블 선택에 따른 최소 스패닝 트리 문제, 즉 정점 레이블 선택에 따라 각 간선의 가중치가 달라질 수 있는 정점 레이블 그래프의 최소 스패닝 트리를 찾는 문제를 연구합니다. 끝납니다. 이 문제는 수학적 OCR에 적용할 때 특히 중요합니다. 문제는 NP-hard인 것으로 나타났습니다. 그러나 수학적 OCR에 적용하려면 트리 너비가 작은 그래프만 처리하면 충분합니다. 본 논문에서는 직렬-병렬 그래프를 위한 선형 시간 알고리즘을 제시합니다. 라벨 선택에 관한 최소 스패닝 트리 문제는 일반화된 최소 스패닝 트리 문제와 밀접한 관련이 있으므로 이들의 관계를 논의한다.
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.
부
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
부
@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},}
부
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 -