## Search found 15 matches

- Fri Jun 05, 2009 12:05 am
- Forum: Algorithms
- Topic: d-division of G with d small as possibl
- Replies:
**0** - Views:
**1675**

### d-division of G with d small as possibl

Can one help me to solve this puzzle please there will be G=(V,E) not directed graph that its vertices V={v1...,vn} appear in this order on the axis of Real numbers (for every 1<=i<j<=n vi appears before vj). a d-division of the vertices of G is a division of them to d different sections, meaning of...

- Wed May 06, 2009 8:26 pm
- Forum: Algorithms
- Topic: calculates a set of nodes
- Replies:
**1** - Views:
**1565**

### calculates a set of nodes

In a direct graph calculates a set U of nodes (u maximal) such there is a path (not necessarily simple) that passes via all U nodes .

Can anyone suggest to which broader category of algorithms this problem can belong to

Can anyone suggest to which broader category of algorithms this problem can belong to

- Mon Apr 13, 2009 11:58 am
- Forum: Algorithms
- Topic: shortest paths network
- Replies:
**2** - Views:
**1743**

### Re: shortest paths network

Thank's for ideas

- Sun Apr 05, 2009 7:54 pm
- Forum: Algorithms
- Topic: shortest paths network
- Replies:
**2** - Views:
**1743**

### shortest paths network

In a network i want to find the number of alternate shortes paths from a start node to all other nodes. Normally Dijkstra can be used. But because there are no weights BFS should also working. I can modify BFS algorithm so that pred (n) doesn't only store one predecessor but a list of possible prede...

- Wed Jan 14, 2009 12:20 am
- Forum: Algorithms
- Topic: hortest path from s to t with which includes all subset
- Replies:
**11** - Views:
**2372**

### Re: hortest path from s to t with which includes all subset

Hi many thanks for your help. but i'm trying to understand the technique u described. for the moment for me looks ofuscated . hwy 2^K factor. I think that we may have k! masks (all permutation of the k nodes.) I was thinking to something like calculate the distance between the two subraphs : (start_...

- Tue Jan 13, 2009 11:55 pm
- Forum: Algorithms
- Topic: path
- Replies:
**2** - Views:
**1164**

### Re: path

Hi many thanks for your help. but i'm trying to understand the technique u described. for the moment for me looks ofuscated . hwy 2^K factor. I think that we may have k! masks (all permutation of the k nodes.) I was thinking to something like calculate the distance between the two subraphs : (start_...

- Tue Jan 13, 2009 12:06 am
- Forum: Algorithms
- Topic: path
- Replies:
**2** - Views:
**1164**

### path

I have a undirected graph

One node is labelled 'start', one is 'end', and there's about a dozen labelled 'mustpass'.

I need to find the shortest path through this graph that starts at 'start', ends at 'end', and passes through all of the 'mustpass' nodes (in any order).

One node is labelled 'start', one is 'end', and there's about a dozen labelled 'mustpass'.

I need to find the shortest path through this graph that starts at 'start', ends at 'end', and passes through all of the 'mustpass' nodes (in any order).

- Mon Jan 05, 2009 11:34 pm
- Forum: Algorithms
- Topic: hortest path from s to t with which includes all subset
- Replies:
**11** - Views:
**2372**

### hortest path from s to t with which includes all subset

In graphs (V,E) with negative edge weights but with no negative cycles , X <V and s, t in V .

I need an algorithm to decide if exist in the graph shortest path from s to t with

which includes all the nodes from X

i've tried to modify A* , Bellman-Ford algorithms but without success .

I need an algorithm to decide if exist in the graph shortest path from s to t with

which includes all the nodes from X

i've tried to modify A* , Bellman-Ford algorithms but without success .

- Fri Jan 02, 2009 12:35 pm
- Forum: Algorithms
- Topic: edge in all the shortest paths
- Replies:
**3** - Views:
**1069**

### Re: edge in all the shortest paths

I think this is a very smart idea! Thanks.

- Fri Jan 02, 2009 11:32 am
- Forum: Algorithms
- Topic: edge in all the shortest paths
- Replies:
**3** - Views:
**1069**

### edge in all the shortest paths

Please give in your ideas and suggestions for best algorithm on the following problems : We have a graph G=(V,E) and a function of weight on the edges w:E->R we have a couple of two vertexes s,t and an edge e we suppose that there is not cycle with a negative weight find an algorithm that determines...

- Sun Dec 21, 2008 1:04 am
- Forum: Algorithms
- Topic: Minimum spanning tree
- Replies:
**9** - Views:
**4207**

### Re: Minimum spanning tree

Thanks for the ideas of solving. Kruskal's algorithm goes like this: it loops over graph's edges in order of increasing cost, and adds current edge to the MST, unless doing so would create a cycle in it. When some edges have equal cost, the algorithm is indeterministic: by changing the order in whic...

- Sun Dec 21, 2008 12:52 am
- Forum: Algorithms
- Topic: Minimum spanning tree
- Replies:
**9** - Views:
**4207**

### Re: Minimum spanning tree

Can someone suggest some good algorithm for this ?

- Sun Dec 21, 2008 12:22 am
- Forum: Algorithms
- Topic: Minimum spanning tree
- Replies:
**9** - Views:
**4207**

### Re: Minimum spanning tree

Which would be modifications in the algorithm's Kruskal?

- Sat Dec 20, 2008 11:50 pm
- Forum: Algorithms
- Topic: Minimum spanning tree
- Replies:
**9** - Views:
**4207**

### Re: Minimum spanning tree

So you think I can use KrusKal to enumerate 2nd MST ?

Why kruskal and not PRIM

Why kruskal and not PRIM

- Sat Dec 20, 2008 8:18 pm
- Forum: Algorithms
- Topic: Minimum spanning tree
- Replies:
**9** - Views:
**4207**

### Minimum spanning tree

How can I solve this?

g(v,e) undirected with weight >=0

give an algorithm which test

if G has Minimum spanning tree uniq

two MST

g(v,e) undirected with weight >=0

give an algorithm which test

if G has Minimum spanning tree uniq

two MST