Minimum Spanning Tree Problem with Label Selection

• FUJIYOSHI Akio

  Department of Computer and Information Sciences, Ibaraki University

• SUZUKI Masakazu

  Graduate School of Mathematics, Kyushu University

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.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E94-D (2), 233-239, 2011

  The Institute of Electronics, Information and Communication Engineers

Keywords

• minimum spanning tree problem
• NP-hardness
• series-parallel graph
• mathematical OCR

Details

• CRID: 1390001204378334848
• NII Article ID: 130000453884
• DOI: 10.1587/transinf.e94.d.233
• ISSN: 17451361
• ISSN: 09168532
• Web Site: http://www.jstage.jst.go.jp/article/transinf/E94.D/2/E94.D_2_233/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed