A modified version of minimum spanning tree

yaoziyuan_at_gmail.com
Date: 02/26/05 

Date: 26 Feb 2005 00:17:35 -0800

I have conceived a modified version of MST. I don't know if it's
already proposed and/or researched by others. The problem is here:

Given a graph G=(V,E) and a subset V' of V, find a tree T in G that
covers V' and has minimum total length. Note that this tree can include
other vertices than V' and any edges in G.

I have also made a similar geometry problem:

Given a set of points P on a plane, find another set of points Q and a
set of straight lines L that connect necessary points in the union set
of P and Q, so that all points in P are connected as a tree T and T has
minimum total length (in geometric distance).

Could anyone analyze these problems?

Best Regards,
Yao Ziyuan

Relevant Pages