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

Hi
you please look into the Book "Introducntion to algorithm by Cormen"
Is has the algo for longest common subsequence whcih may be useful for
you .
or you can look for the Minimum spanning tree or the travelling
salesman problem / you can look for Kruskal and Prim's algo...
If you dont have the book please let me know I ll mail it to you

Mayur

tomnab@xxxxxxxxx wrote:
> Hello,
>
> I'm a French researcher in the field of Petri Nets. For short, PNs are
> a tool to model discrete event systems. The behavior of a PN can be
> formulated into a reachability graph : a directed, connex graph, where
> circuits may exist.
>
> In the case of bounded PNs, the reachability graph is finite, and I
> want to compute the longest simple path of this graph, starting from
> one particular vertice. Note I do not know any "target" vertice.
>
> Since I'm not really aware of graph theory, I'd like to know the exact
> denomination of this problem, its complexity, and of course some
> references about the corresponding results. While searching on the
> internet, I found that :
>
> * The search for an hamiltonian path in this type of graph is NP
> complete (but in my case I do not want to use automatically the whole
> set of vertices);
> * The search for a longest path between two KNOWN vertices is NP
> complete (with a reference to the HamPath Problem that I do not
> understand since nothing in "longest path" means "all the vertices"
> like in Hamiltonian pbs...)
>
> I'd like to know if I have well understood the previous assertions, if
> I can say that my problem is NP complete, and the corresponding
> references and arguments...
>
> Thanks for your comments, and please forgive my poor english &
> knowlegde...
>
> T. Bourdeaud'huy

.

Relevant Pages

  • Complexity of Finding the longest simple path in a graph
    ... formulated into a reachability graph: ... In the case of bounded PNs, the reachability graph is finite, and I ... Note I do not know any "target" vertice. ... references about the corresponding results. ...
    (comp.theory)
  • Re: Calling destructor
    ... >> Something you can do, that will help, is to set references to null for ... As long as you hold references to an object, ... OP described how he had a large graph of objects and needed the ability to ... In such a scenario, setting a reference to the object to null ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Problem about Dijkstras Min Path Algorithm
    ... I used one vector that stated the number of edges connecting a vertice. ... with the help of auxiliary vector to state if a vertice was already used or not I think I managed to implement Dijkstra's algorithm. ... You now just need to convert your data in this format instead of using the adjacency matrix. ... P.S. - Graph theory is not exactly my field of work... ...
    (comp.soft-sys.matlab)
  • Re: maximal 3-colorable subset
    ... johank wrote: ... a optimisation variant of graph coloring that fixes the number ... # difficulties finding references that address such problems. ...
    (comp.theory)
  • Re: White House spins "The Commander Guy"
    ... References you ... That's the true test of science -- ... The graph shows a scatter anywhere between 110 and 130. ... science is to consider all data, and that scatter graph has more data ...
    (rec.sport.golf)