[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

1695.0. "Steiner Tree Algorithm?" by CX3PT2::KOWTOW::J_MARSH () Mon Nov 30 1992 13:30

    Can someone point me to an algorithm for finding the Steiner tree for a
    collection of points?  A Steiner tree is the tree connecting all points
    that minimizes the total length of all the branches, but you're allowed
    to add points to make the length smaller.

    I know this is one of those difficult problems (NP-hard?) and it is
    impractical to try to compute the Steiner tree for many points.  I'm
    looking for an algorithm that will work for a small number of points
    (4, 5, or 6) and it is OK if the algorithm fails for certain unusual
    sets of points.  Thanks...

    -- Jeff

T.R	Title	User	Personal Name	Date	Lines
1695.1		AUSSIE::GARSON		`Mon Nov 30 1992 21:04`	3
	re .0 Did you try HEAVY::ALGORITHMS? KP7 etc.