Branching trees cliqueにおける部分重み付け関数の最節約拡張

A study on most-parsimonious extensions of partial assignments on a branching trees clique

Let G be a connected simple graph with a vertex set V, an edge set E. Let G_{σ} be a graph G with a partial assignment maps from a subset U of V into the real number R. For a given G_{σ}, an assignment λ from V into R such that λ(u)=σ(u) for each u in U, is called an extension of σ on G. For an extension λ of σ, we define the length L_{λ}(e) of an edge e={u,v} on λ by |λ(u)－λ(v)|, the length L_{λ}(G_{σ}) of G_{σ} on λ by Σ_{e} in E L_{λ}(e), respectively. Furthermore, L^{*}(G_{σ}) is defined by the minimum value of L_{μ}(G_{σ}) for any extension μ of σ, and an extension λ of σ such that L_{λ}(G_{σ})=L^{*}(G_{σ}) is called an most-parsimonious extension (abbreviated to MPE) on G_{σ}. We call the problems on this minimization the MPE problems.

From a mathematical point of view, D. F. Robinson (1973) has introduced these problems, and shown a polynomial time algorithm on the number of vertices for obtaining a MPE. On the other hand, from a phylogenetic point of view, J. M. Farris (1970), D. L. Swofford and W. P. Maddison (1987) have dealt with the problems on completely bifurcating phylogenetic trees and shown a solution. M. Hanazawa et al. (1995) have mathematically formulated the problems for the case of which G is a tree, and presented clear algorithms for those. Note that we have a gap between the Robinson method and the Hanazawa et al. one. Therefore, M. Hanazawa and H. Narushima (1999), K. Miyakawa and H. Narushima (2008) have extended the MPR problems for the case of which G is a graph having only one cycle, called a unicycle graph, and shown a linear time algorithm for solving the problems. In this paper, we deal with the MPE problems for a graph which consists of a complete graph and some trees, called a branching trees clique, and show some propositions.