Re: Graph theory problem
- From: Barb Knox <see@xxxxxxxxx>
- Date: Tue, 22 Aug 2006 10:24:46 +1200
In article <1156194250.826872.126270@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"Rij" <rij.ghosh@xxxxxxxxx> wrote:
Let G have even no. of nodes. I want to eventually merge all nodes into
1. At each step, I will merge any two nodes. The cost of each merge is
the weight
of the edge common to the two vertices. The cost at each step is the
sum of the cost of all such merges. I want to minimize the cost over
all the steps.
So, the total cost after all the steps is the sum of the weights of all
the edges that have been eliminated. Since eventually you want to end
up with just 1 node, you will eliminate ALL edges except the one edge
(if any) from that node to itself. So, pick a node with no edge to
itself, or if there isn't any then a node with the minimum-weight such
edge, and let that be your final node. Then ANY pattern of merges
ending with just that node will have the same cost, which is the minimum.
Does this sound like any common graph theoretic problem? You can assume.
edges are undirected and the graph to be fully connected if that makes
life easy.
Thanks in advance
- References:
- Graph theory problem
- From: Rij
- Graph theory problem
- Prev by Date: Re: Graph theory problem
- Next by Date: Re: basic query regarding NP Complete...
- Previous by thread: Re: Graph theory problem
- Next by thread: Turing completeness, and generation of non-Turing complete code to solve problems that would typically require Turing complete languages
- Index(es):
Relevant Pages
|
