Search found 15 matches

by nicoletsg
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...
by nicoletsg
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
by nicoletsg
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
by nicoletsg
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...
by nicoletsg
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_...
by nicoletsg
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_...
by nicoletsg
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).
by nicoletsg
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 .
by nicoletsg
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.
by nicoletsg
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...
by nicoletsg
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...
by nicoletsg
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 ?
by nicoletsg
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?
by nicoletsg
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
by nicoletsg
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

Go to advanced search