No label defined (Q3740256)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3974318
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3974318

      Statements

      0 references
      1985
      0 references
      [For the entire collection see Zbl 0556.00015.] We study the complexity of finding long paths in directed or undirected graphs. Given a graph \(G=(V,E)\) and a number k, our algorithm decides within time O(k!\(\cdot | V| \cdot | E|)\) for all u,v\(\in V\) whether there exists some path of length k from u to v. The complexity of this algorithm has to be compared with \(O(| V|^{k-1}\cdot | E|)\) which is the worst case behaviour of the algorithms described up to now in the literature. We get similar results for the problems of finding a longest path, a cycle of length k or a longest cycle, respectively. Our approach is based on the idea of representing certain families of sets by subfamilies of small cardinality. We also discuss the border lines of this idea.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references