Velocity Reviews > Java > Re: Graphs

# Re: Graphs

Roedy Green
Guest
Posts: n/a

 08-16-2003
On Sat, 16 Aug 2003 22:02:06 +0200, "Dan Peder Eriksen"
<(E-Mail Removed)> wrote or quoted :

>I'm having a problem with figuring out how to handle this problem:
>* I have X nodes.
>* Each node is connected(the connection goes both ways) to 1 or more nodes.
>* Every connection has a value.
>
>What I need to do is to remove connections so every node only is connected
>to one other node.
>The problem is that the sum of all the connections that remain should be the
>lowest possible value.

See http://mindprod.com/jgloss/knuth.html

Nearly always that guy has an algorithm. This is amazing considering
how long ago the books were written.

--
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Dan Peder Eriksen
Guest
Posts: n/a

 08-16-2003

"Roedy Green" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Sat, 16 Aug 2003 22:02:06 +0200, "Dan Peder Eriksen"
> <(E-Mail Removed)> wrote or quoted :
>
> >I'm having a problem with figuring out how to handle this problem:
> >* I have X nodes.
> >* Each node is connected(the connection goes both ways) to 1 or more

nodes.
> >* Every connection has a value.
> >
> >What I need to do is to remove connections so every node only is

connected
> >to one other node.
> >The problem is that the sum of all the connections that remain should be

the
> >lowest possible value.

>
> See http://mindprod.com/jgloss/knuth.html
>
> Nearly always that guy has an algorithm. This is amazing considering
> how long ago the books were written.

>
> --
> Canadian Mind Products, Roedy Green.
> Coaching, problem solving, economical contract programming.
> See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.