Author(s)： Akio Fujiyoshi and Masakazu Suzuki

J. Math-for-Ind. 2B (2010) 183-197.

• File： JMI2010B-8.pdf (973KB)

Abstract
In this paper, we introduce a variation of the minimum spanning tree problem for the application to mathematical OCR. The problem is obtained from the original minimum spanning tree problem by importing the notions of "candidate selection" and "link-label selection." It is shown that the problem is NP-hard. However, we find that, for the application to mathematical OCR, it is sufficient to deal with only a class of graphs that is recursively defined with some graph-rewriting rules. For the class of graphs, it is shown that the problem can be solved in linear-time in the number of vertices of a graph.

Keyword(s).　 the minimum spanning tree problem, NP-completeness, treewidth, mathematical OCR, mathematical formula recognition