From: David Newsgroups: sci.math Subject: Re: graph theory question Date: 14 Dec 1998 17:41:48 GMT In article <7536bp$s75$1@scotsman.ed.ac.uk> Emma Hart, emmah@dai.ed.ac.uk writes: >Hi, > >I have the following graph problem I need to solve - I am not a >mathematician and would like to find out if this a common problem >area, and if there are recognised algorithms/techniques for solving >such problems: > > >I have a graph G with V vertices. Each vertex is connected to every >other vertex by an edge which has an associated cost or weight, w. > >There is specific subset of the V vertices, V'. I wish to find a tree >on G that spans these V' vertices, and has minimal cost, i.e the sum >of the weights associated with each edge in the spanning tree is >minimal. The tree can include as many of the other (V-V') vertices as >is necessary. > >The graph itself is not 2-Dimensional, i.e I cannot give a cartesian >coordinate to each vertex, and calculate distance between vertices in >the geometric sense. The weight associated with each edge is not >related to geometric distance. Finding a minimum weight tree (MWST) that spans all the vertices in V is simple -- grow your tree edge-by-edge by iteratively picking (from the remaining edges) the smallest-weight edge that will not create a cycle in the tree. This is Kruskal's algorithm, and it will always find a MWST on the vertices in V. The question now is, how do you find a MWST that spans V'. I don't know of an algorithm for this, but a few thoughts come to mind. If you find a MWST on V, then delete all leaves of the tree that are not in V', this will probably produce a MWST on V' in some cases. If the number of vertices in V' is close to the number of vertices in V, then it probably won't take too much analysis to determine whether it is actually a MWST on V'. David ============================================================================== From: chavey@beloit.edu (Darrah Chavey) Newsgroups: sci.math Subject: Re: graph theory question Date: Thu, 17 Dec 1998 13:06:00 -0600 In article <7536bp$s75$1@scotsman.ed.ac.uk>, emmah@dai.ed.ac.uk (Emma Hart) wrote: > I have a graph G with V vertices. Each vertex is connected to every > other vertex by an edge which has an associated cost or weight, w. > > There is specific subset of the V vertices, V'. I wish to find a tree > on G that spans these V' vertices, and has minimal cost, i.e the sum > of the weights associated with each edge in the spanning tree is > minimal. The tree can include as many of the other (V-V') vertices as > is necessary. David gave an algorithm that gets an approximate answer, but one that is not always minimal. Finding a minimal answer is NP-Complete, i.e. it is extremely time-consuming to solve. (Proven by R.M. Karp, in "Complexity of Computer Computations, ed. Miller & Thatcher, 1972, pp. 85-103. See also "Computers and Intractability" by Garey & Johnson, 1979, p. 208, problem ND12.) Since the problem is NP-Complete, there is no reasonable chance of finding a sub-exponential algorithm to find the exact answer. An exponential algorithm is: For each subset W of the vertices (V-V'), check if the subgraph induced by W + V' is connected. If it is, find the minimum cost spanning tree of that graph. Take the minimum of all the answers you find this way. --Darrah Chavey Department of Math & Computer Science chavey@beloit.edu Beloit College; 700 College St; Beloit, Wisc. (608)-363-2220 http://www.beloit.edu/~chavey 53511 -- One tequila, two tequila, three tequila, floor.