Minimum cycle bases, faster and simpler

DOI10.1145/1644015.1644023MaRDI QIDQ6486930zbMATH OpenOpenAlexFDO

Authors K. Mehlhorn, Dimitrios Michail

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1644015.1644023

zbMATH Keywords

cycle spaceminimum cycle basissparse basis

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs
• New Approximation Algorithms for Minimum Cycle Bases of Graphs
• New approximation algorithms for minimum cycle bases of graphs
• Faster Algorithms for Minimum Cycle Basis in Directed Graphs
• Automata, Languages and Programming

Cited in

(32)

• An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs
• Integral cycle bases for cyclic timetabling
• On finding a cycle basis with a shortest maximal cycle
• Length bounds for cycle bases of graphs
• Minimum cycle bases of weighted outerplanar graphs
• Minimum cycle bases for network graphs
• Assigning papers to referees
• The lattice of cycles of an undirected graph
• New length bounds for cycle bases
• Fair matchings and related problems
• Minimum Path Bases
• Faster Algorithms for Minimum Cycle Basis in Directed Graphs
• Rooted cycle bases
• On optimal cycle bases of graphs for mesh analysis of networks
• Implementing minimum cycle basis algorithms
• Minimum Cycle Bases in Graphs Algorithms and Applications
• New Approximation Algorithms for Minimum Cycle Bases of Graphs
• Minimum Cycle Bases and Their Applications
• Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• scientific article; zbMATH DE number 2080984 (Why is no real title available?)
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• A novel technique for cohomology computations in engineering practice
• Flow and Elastic Networks on the 𝑛-Torus: Geometry, Analysis, and Computation
• Rooted cycle bases
• An improved heuristic for computing short integral cycle bases
• Automata, Languages and Programming
• Experimental and Efficient Algorithms
• Computing cyclic invariants for molecular graphs
• Fast algorithms for minimum homology basis
• Properties of Gomory-Hu co-cycle bases
• Classes of cycle bases

This page was built for publication: Minimum cycle bases, faster and simpler

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