An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs

DOI10.1007/s00453-007-9064-zzbMath1163.68329OpenAlexW2124619812MaRDI QIDQ1006382

Telikepalli Kavitha, Dimitrios Michail, Katarzyna E. Paluch, Kurt Mehlhorn

Publication date: 24 March 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9064-z

zbMATH Keywords

Polynomial algorithmsMatrix multiplicationCycle basisCycle space

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Minimum strictly fundamental cycle bases of planar graphs are hard to find ⋮ Cycle analysis of directed acyclic graphs ⋮ Satisfiability checking in Łukasiewicz logic as finite constraint satisfaction ⋮ Minimum cycle bases of weighted outerplanar graphs ⋮ Computational homology to unravel the complex scar structure after a myocardial infarction ⋮ New approximation algorithms for minimum cycle bases of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• All pairs shortest paths for graphs with small integer length edges
• All-Pairs Small-Stretch Paths
• Minimum Path Bases
• Undirected single-source shortest paths with positive integer weights in linear time
• New Approximation Algorithms for Minimum Cycle Bases of Graphs
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Algorithms for Generating Fundamental Cycles in a Graph
• Odd Minimum Cut-Sets and b-Matchings
• Cycle bases of minimal measure for the structural analysis of skeletal structures by the flexibility method
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
• Floats, Integers, and Single Source Shortest Paths
• Experimental and Efficient Algorithms