Minimum Spanning Tree Problem with Label Selection

Akio FUJIYOSHI  Masakazu SUZUKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E94-D   No.2   pp.233-239
Publication Date: 2011/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E94.D.233
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
Category: 
Keyword: 
minimum spanning tree problem,  NP-hardness,  series-parallel graph,  mathematical OCR,  

Full Text: PDF>>
Buy this Article




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.