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

DOI10.1007/s00453-007-9064-zzbMath1163.68329MaRDI 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 algorithms; Matrix multiplication; Cycle basis; Cycle space

Mathematics Subject Classification ID

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

Related Items

Minimum strictly fundamental cycle bases of planar graphs are hard to find, Satisfiability checking in Łukasiewicz logic as finite constraint satisfaction, New approximation algorithms for minimum cycle bases of graphs, Minimum cycle bases of weighted outerplanar 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