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

cycle basisfast matrix multiplicationrandomizationshortest paths

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)

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

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)