Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $G=(V,E)$ be a undirected simple graph, and $\Omega(G)$ denote the set of spanning trees of G. Does the next funcion $$l(G) = \min_{T \in \Omega(G)}\quad \sum_{uv \in E} \mbox{dist}_T(u,v)$$ have a specific name? Or has it been studied before?.

The problem is NP-hard, but I'm particularly interested in lower bounds of $l(G)$. Both for general graphs and for specific topologies.

share|cite|improve this question
I think this problem is exactly the same as the one here. –  user2033412 Aug 17 '13 at 14:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.