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
1985
0 references
0.8540564179420471
0 references
0.8507847189903259
0 references
0.8327459096908569
0 references
0.8262397050857544
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