PUB - Publikationen an der Universität Bielefeld

This chapter introduces a novel class of graphs: Minimum Spanning Markovian Trees (MSMT). The idea behind MSMTs is to provide spanning trees that minimize the costs of edge traversals in a Markovian manner, that is, in terms of the path starting with the root of the tree and ending at the vertex under consideration. In a second part, the chapter generalizes this class of spanning trees in order to allow for damped Markovian effects in the course of spanning. These two effects - that is, (i) the sensitivity to the contexts generated by consecutive edges and (ii) the decreasing impact of more antecedent (or "weakly remembered") vertices - are well-known in cognitive modeling (Gaerdenfors, 2000; Kintsch, 1998; Murphy, 2002; Sharkey and Sharkey, 1992}. In this sense, the chapter can also be read as an effort to introduce a graph-model to support the simulation of cognitive systems. Note that MSMTs are not to be confused with branching Markov chains or Markov trees (Menshikov and Volkov 1997} as we focus on generating spanning trees from given weighted undirected networks.