scientific article; zbMATH DE number 3974318

From MaRDI portal
Publication:3740256





[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.




Cited in
(59)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3740256)