## 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
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).
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 .
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
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