scientific article; zbMATH DE number 3876619
[For the entire collection see Zbl 0527.00032.] The problem of determining a shortest cycle is wellknown to be computable in time \(O(| V|\cdot | E|)\) in the case of unweighted graphs and in time \(O(| V|^ 3)\) in the case of graphs with edge weights. In this paper three algorithms are presented: (1) An algorithm computing the shortest cycle of odd length in an undirected graph without edge weights within time \(O(| E|\cdot | V|)\) (this algorithm is based on breadth-first-search). (2) An algorithm computing the shortest cycle of odd length in a (directed or undirected) graph with edge weights within time \(O(| V|^ 3)\) (this algorithm is based in Dijkstra's algorithm). (3) An algorithm computing the shortest cycle of even length in an undirected graph without edge weights within time \(O(| V|^ 2\cdot\min \{A(| V|),\lambda (G)\}),\) where A is the inverse Ackermann function and \(\lambda\) (G) is the length of the shortest cycle of even length. The first two algorithms don't use essential new ideas. Algorithm (3) uses complex techniques and has to be viewed as the main result of this paper.
- An efficient Dijkstra-like labeling method for computing shortest odd/even paths
- An inherently iterative computation of Ackermann's function
- A shortest cycle for each vertex of a graph
- The even-path problem for graphs and digraphs
- Finding Even Cycles Even Faster
- Finding even cycles even faster
- Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
- scientific article; zbMATH DE number 3231691 (Why is no real title available?)
- LATIN 2004: Theoretical Informatics
- Finding shorter cycles in a weighted graph
- Shortest odd paths in undirected graphs with conservative weight functions
- Finding a shortest cycle in a subspace of the cycle space of a graph
- Algorithms for shortest paths and d-cycle problems
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 Q3341925)