scientific article; zbMATH DE number 3974318
[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.
- A parameterized view on matroid optimization problems
- On the complexity of database queries
- On problems with short certificates
- Complexity of searching an immobile hider in a graph
- Finding even subgraphs even faster
- Long directed \((s,t)\)-path: FPT algorithm
- A faster parameterized algorithm for temporal matching
- Revising Johnson's table for the 21st century
- Faster deterministic parameterized algorithm for k-path
- Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Narrow sieves for parameterized paths and packings
- Finding a smallest odd hole in a claw-free graph using global structure
- QUBO formulations of the longest path problem
- Gerrymandering on graphs: computational complexity and parameterized algorithms
- Parameterized complexity and subexponential-time computability
- Deterministic algorithms for matching and packing problems based on representative sets
- Deterministic subgraph detection in broadcast CONGEST
- The even-path problem for graphs and digraphs
- Spotting trees with few leaves
- Mixing Color Coding-Related Techniques
- scientific article; zbMATH DE number 3912415 (Why is no real title available?)
- On longest paths in digraphs
- scientific article; zbMATH DE number 682567 (Why is no real title available?)
- Finding a Path of Superlogarithmic Length
- A streaming algorithm for the undirected longest path problem
- Finding even cycles even faster
- scientific article; zbMATH DE number 2119679 (Why is no real title available?)
- Finding detours is fixed-parameter tractable
- On approximating the longest path in a graph
- Going far from degeneracy
- Scheduling for single agile satellite, redundant targets problem using complex networks theory
- Finding detours is fixed-parameter tractable
- Spotting trees with few leaves
- Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
- Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
- The \(k\)-distinct language: parameterized automata constructions
- Finding monotone paths in edge-ordered graphs
- Counting Homomorphic Cycles in Degenerate Graphs
- Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
- Multistage \(s-t\) path: confronting similarity with dissimilarity
- Detours in directed graphs
- Parameterized algorithms for list \(K\)-cycle
- AntiFactor is FPT parameterized by treewidth and list size (but counting is hard)
- A theory of even functionals and their algorithmic applications
- Finding and counting given length cycles
- Hitting long directed cycles is fixed-parameter tractable
- Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results
- Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. II: Hardness results
- Anti-factor is FPT parameterized by treewidth and list size (but counting is hard)
- Forgetfulness can make you faster: an O^*(8.097ᵏ)-time algorithm for weighted 3-set k-packing
- Approximating the longest paths in grid graphs
- Deterministic even-cycle detection in broadcast CONGEST
- Maintaining longest paths incrementally
- Algorithms for long paths in graphs
- Representative families: a unified tradeoff-based approach
- Main-memory triangle computations for very large (sparse (power-law)) graphs
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
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)