A variation of the minimum spanning tree problem for the application to mathematical OCR

MI: Global COE Program Education-and-Research Hub for Mathematics-for-IndustryグローバルCOEプログラム「マス･フォア･インダストリ教育研究拠点」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 \u22candidate selection\u22 and \u22link-label selection.\u22 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 graphrewriting 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