scientific article; zbMATH DE number 3876619

From MaRDI portal
Publication:3341925





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











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)