Faster Algorithms for Minimum Cycle Basis in Directed Graphs

DOI10.1137/060670730MaRDI QIDQ3395038zbMATH OpenOpenAlexFDO

Authors Ramesh Hariharan, Telikepalli Kavitha, K. Mehlhorn

Publication date 20 August 2009

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/c277fecf2b4070a1449a67c50e8efc08430055fd

zbMATH Keywords

randomizationshortest pathsfast matrix multiplicationcycle basis

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
• Automata, Languages and Programming
• Algorithms to compute minimum cycle basis in directed graphs
• Minimum cycle bases, faster and simpler
• Automata, Languages and Programming

Cited in

(18)

• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
• Cycle analysis of directed acyclic graphs
• Automata, Languages and Programming
• Algorithms to compute minimum cycle basis in directed graphs
• A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
• scientific article; zbMATH DE number 7204576 (Why is no real title available?)
• Automata, Languages and Programming
• Minimum Cycle Bases in Graphs Algorithms and Applications
• Minimum Cycle Bases and Their Applications
• scientific article; zbMATH DE number 7760193 (Why is no real title available?)
• An O(nm) time algorithm for finding the min length directed cycle in a graph
• A cycle-based formulation and valid inequalities for DC power transmission problems with switching
• STACS 2005
• A greedy approach to compute a minimum cycle basis of a directed graph
• Minimum cycle bases, faster and simpler
• Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs
• Collusion in atomic splittable routing games

This page was built for publication: Faster Algorithms for Minimum Cycle Basis in Directed Graphs

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