Minimum Spanning Tree Problem with Label Selection
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E94-D No.2 pp.233-239
- Publication Date
- 2011/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E94.D.233
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
