Faster Algorithms for Minimum Cycle Basis in Directed Graphs

DOI10.1137/060670730zbMath1178.68669OpenAlexW2144071845MaRDI QIDQ3395038

Telikepalli Kavitha, Kurt Mehlhorn, Ramesh Hariharan

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 pathscycle basisfast matrix multiplication

Mathematics Subject Classification ID

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

Related Items (4)

Cycle analysis of directed acyclic graphs ⋮ Collusion in atomic splittable routing games ⋮ Minimum Cycle Bases and Their Applications ⋮ A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching

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