graph question - need some help...
- From: "kiwi" <kshoyer@xxxxxxxxx>
- Date: 21 Apr 2005 13:53:42 -0700
Hi All,
I need to solve the following problem. I have a direct weighted (edge)
graph, and set of "origin" nodes.
There are 2 special characteristics to the graph:
1) Part of the origin nodes are "split" into 2 nodes- vi and vi'-
(their union represent just 1 node.-> vi)
2) Some nodes doesn't have incoming edges. We will call these nodes-
initiators and the have some weigh associated with them.
I want to visit all the node (for nodes that were split i can visit vi
or vi' (or both), and for initiator's node i must pay their weight) in
the minimum cost.
for nodes that are not initiators- i MUST use the edges from the graph.
Output: given the knowledge about the graph(nodes,split,initiator and
weights) i want a list of nodes to visit them and the total cost.
For example: this graph includes 5 origin nodes: v1 ,v2...v5
1) v2,v4,v5 are splits into v2,v2',v4,v4' and v5,v5'.
2) v1 and v3 are initiators. v1 weight is (a+x1) and v3 is also (a+x1).
3) the transitions cost from node ni to nj, are in the matrix below:
moving from v2 to v4 is: (a+x2)
the empty cells mean that there is no edge between the nodes.
to
v1 v2 v2' v3 v4 v4' v5 v5'
f v1 x2
v2 a (a+x2) (a+x2)
v2' 0 0
v3 x2 x2
v4 a (a+x2)
v4' 0
v5 a
v5'
Generally, how should i solve this problem, what is the complexity of
this problem? Does anyone know any good reference ?
any help will be appreciated,
Kiwi
.
- Prev by Date: can anybody show me the math why differential entropy of a mixed-type distribution is -infinity?
- Next by Date: Re: JSH: Easy one way, hard the other
- Previous by thread: can anybody show me the math why differential entropy of a mixed-type distribution is -infinity?
- Next by thread: analysis question
- Index(es):
Relevant Pages
|
