Re: Complexity of Finding the longest simple path in a graph

It's me again... for a precision. The reachability graph is not
weighted : each arc has the same "weight"... Thus I'm searching for the
longest path w.r.t. the number of "steps" that can be made without
getting a vertice already found. If it was a tree, it would be the
height of the tree, but here it is not a tree...

I hope this remark will help... Can I again speak of "longest path" if
all weights are the same or should I call my problem "graph height" ?

Faithfully,

Tom.

.

Relevant Pages

  • Re: Finding longest path between two vertices
    ... people use for "shortest path" won't work. ... Bellman-Ford also works with negative weights, has long as there is no cycle of negative weight. ... Why won't Bellman-Ford algorithm work with all weights -1 (apart from cycles)? ... It should work for longest path. ...
    (comp.theory)
  • Re: Finding longest path between two vertices
    ... I have a directed graph with weighted edges (weights are all positive). ... I'm looking for an efficient algorithm to find the longest path ...
    (comp.theory)
  • Re: Finding longest path in graph between two vertices
    ... I have a directed graph with weighted edges (weights are all positive). ... I'm looking for an efficient algorithm to find the longest path ...
    (sci.math)
  • Re: Finding longest path between two vertices
    ... Instead of negating the weights w you may try 1/w (all weights are ... shortest path which should be longest path with weights w ... I'm looking for an efficient algorithm to find the longest path ...
    (comp.theory)