# interesting graph question- need some help..

*From*: "kiwi" <kshoyer@xxxxxxxxx>*Date*: 26 Apr 2005 11:17:22 -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 "origin" nodes:

1) Part of the origin nodes are "split" into 2 nodes- vi and vi'-

(their union represent just 1 node.-> vi). We'll call them "split"

nodes.

2) Some nodes doesn't have incoming edges. We will call these nodes-

"initiators" and the have some weigh associated with them.

i.e each origin node can be a "split" or "initiator" node.

We will call this graph "new" graph.

I have to visit every "initiator" node and at least one (or both) of

every "split" node in the minimum cost.

For the "split" nodes we should be careful:

1) i can't visit vi' without visit vi- always there is a direct edge

from vi to vi'. (it means that either i can visit them together in the

same component or never visit vi')

2) say that i choose to visit vertex vi but not vi', then it means

that i can "remove" vi' from the list of the vertices because i already

cover the "origin" node of vi and vi'. So i don't have to reconsider

vi' in any other component.

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 transition 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'

here are 2 examples (out of many) of 2 optional paths using

the matrix: (v1' and v3' are initiators)

1) v1' -> v2 -> v4 -> v4' -> v5 : cost- (a+x1)-cost of v1'+

(x2)+(a+x2)+(a)+(0)- transition cost: total: 3a+x1+2x2

2) v3': cost- (a+x1)

total cost: 4a+2x1+2x2

- this example is correct, we cover all origin nodes

or

1) v1' -> v2 -> v5 : cost- (a+x1)-cost of v1'+(x2)+(a+x2)= 2a+x1+2x2

2) v3' -> v4: cost: (a+x1)+(x2)=a+x1+x2

total cost: 3a+2x1+3x2

- this example is correct, we cover all origin nodes

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:
**Time Dependent Shortest Path** - Next by Date:
**Re: overall-longest-possible-path problem** - Previous by thread:
**Time Dependent Shortest Path** - Next by thread:
**n edges shortest path** - Index(es):