I am trying to compare minimum spanning trees through time. I have two questions: 1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure when there is a probability of appearance assigned to each labeled vertex of the trees? It means some vertices might be absent (disappeared) in the future thus the size of the tree might be different. 2-If we knew the Gromov-Hausdorff distance between a known minimum spanning tree and an unknown minimum spanning tree, are we able to build the second tree? Are we able to extract any information about the structure of the second tree (e.g. its length) from the distance measure and the first known tree? Notice that the second tree might have smaller number of vertices due to absence of some vertex.
4
-
$\begingroup$ It would help if you introduce the setting: you seem to be dealing with connected graphs... what kind of graphs? finite? finite degree? arbitrary? $\endgroup$– YCorCommented Jun 11, 2015 at 15:19
-
$\begingroup$ I am studying complete graphs and their minimum spanning trees through the time. Please look at this paper: citeseerx.ist.psu.edu/viewdoc/… My goal is to expand Theorem 1.1 on this paper. The only difference in my case is that I have to take into account the probability of appearance of the vertices. $\endgroup$– SamCommented Jun 11, 2015 at 17:42
-
$\begingroup$ You seem to mean finite complete graphs. $\endgroup$– YCorCommented Jun 11, 2015 at 18:22
-
$\begingroup$ Yes I would like to find the expected length of the minimum spanning tree of a simple, finite and complete graph where edge weights are iid with an arbitrary distribution and each vertex has a probability of presence in the future. $\endgroup$– SamCommented Jun 11, 2015 at 18:33
Add a comment
|