Yes, you are right
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit
Thanks for the pointer. It is not the exact problem I am trying to
solve but should give me a good start.
Topic:
Graph
Theory Problem
Raj
Nov 05 03:11AM -0700 ^
http://en.wikipedia.org/wiki/Graph_partition
--
You received this message because you are sub
http://en.wikipedia.org/wiki/Graph_partition
On Nov 4, 2:23 pm, khaled wrote:
> I have the following graph problem. I would appreciate if some graph
> theory expert points me to what is the scientific name under which it
> is known in graph theory.
>
> Given a directed graph G=(V,E,W) where W is
Since it s a DAG, just multiply all the edge weights by -1. Then use
dijkstra's to find the min shortest path.
Wether some of the edge weights are negative or not, it shouldn't
effect the solution as when using dijkstra's, we take the min node
potentials. ,--- This can be proven
On Aug
On Jun 24, 10:05 am, pramod <[EMAIL PROTECTED]> wrote:
> For DAGs I don't think there's a unique path from a start vertex to
> each vertex reachable from it. There could be many paths.
>
> One way to solve this problem is to topologically sort the DAG and
> start from the end and move backwards
pramod wrote:
> For DAGs I don't think there's a unique path from a start vertex to
> each vertex reachable from it. There could be many paths.
Yes, for a DAG there certainly can be multiple paths to the same node.
I'm afraid I kept forgetting that a DAG is not the same as a tree.
Thank you for
For DAGs I don't think there's a unique path from a start vertex to
each vertex reachable from it. There could be many paths.
One way to solve this problem is to topologically sort the DAG and
start from the end and move backwards till the start vertex and keep
track of the longest path.
The last
kunzmilan wrote:
> On Jun 20, 10:40 am, mirchi <[EMAIL PROTECTED]> wrote:
> > can anyone please tell me how to find
> > single source longest path in a directed acyclic graph??
> Write its adjacency matrix A(ij) = 1, if arc i to j exists, 0
> otherwise.
> Find the consecutive powers A^k.
> When a
On Jun 20, 10:40 am, mirchi <[EMAIL PROTECTED]> wrote:
> can anyone please tell me how to find
> single source longest path in a directed acyclic graph??
Write its adjacency matrix A(ij) = 1, if arc i to j exists, 0
otherwise.
Find the consecutive powers A^k.
When a new nonzero element appears i
>No, longest path isn't that easy. We can find the Halminton path as well as
>the longest path, but...
That's right. I misread the question. I thought the shortest path was being
asked for.
But, since the graph is a DAG, this is actually an easier problem.
There is a unique path from the sourc
No, longest path isn't that easy. We can find the Halminton path as well as
the longest path, but...
On 6/20/07, Muntasir Khan <[EMAIL PROTECTED]> wrote:
>
> On 6/20/07, mirchi <[EMAIL PROTECTED]> wrote:
> >
> >
> > can anyone please tell me how to find
> > single source longest path in a directed
On 6/20/07, mirchi <[EMAIL PROTECTED]> wrote:
>
>
> can anyone please tell me how to find
> single source longest path in a directed acyclic graph??
>
>
> >
>
If all edges are non-negative, you can use Dijkstra's Algorithm. Otherwise a
simple Bellman-Ford should do. But if you are looking for somet
Introduction to Graph Theory by Douglas B. West is a good book which covers lots more chapters like maximal Matching(A more mathematical approach)On 4/20/06,
BiGYaN <[EMAIL PROTECTED]> wrote:
Graph Theoryby, N. DeoIt is a nice book covering almost the entire subject from ground up.And yes, you don
Graph Theory
by, N. Deo
It is a nice book covering almost the entire subject from ground up.
And yes, you don't have to be a CS Major to read this.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks"
Hi,
Introcuction to Algorithms - Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest - this is really very useful one. Also, I can send you
a good text regarding to graph theory if you want.
--~--~-~--~~~---~--~~
You received this message because you are subs
15 matches
Mail list logo
