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.

  • $\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$ – YCor Jun 11 '15 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$ – Sam Jun 11 '15 at 17:42
  • $\begingroup$ You seem to mean finite complete graphs. $\endgroup$ – YCor Jun 11 '15 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$ – Sam Jun 11 '15 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.