Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs

DOI10.1007/978-3-642-13036-6_30MaRDI QIDQ3569834zbMATH OpenOpenAlexFDO

Authors E. Amaldi, Claudio Iuliano, Romeo Rizzi

Publication date 22 June 2010

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13036-6_30

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
• STACS 2005
• Algorithms for finding minimum fundamental cycle bases in graphs
• Automata, Languages and Programming
• Algorithms to compute minimum cycle basis in directed graphs
• Faster Algorithms for Minimum Cycle Basis in Directed Graphs
• An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs
• Minimum Cycle Bases in Graphs Algorithms and Applications
• A greedy approach to compute a minimum cycle basis of a directed graph
• New Approximation Algorithms for Minimum Cycle Bases of Graphs

Cited in

(19)

• Implementing minimum cycle basis algorithms
• Minimum strictly fundamental cycle bases of planar graphs are hard to find
• Edge-swapping algorithms for the minimum fundamental cycle basis problem
• On the approximability of the minimum strictly fundamental cycle basis problem
• New approximation algorithms for minimum cycle bases of graphs
• An efficient algorithm for searching implicit AND/OR graphs with cycles
• Automata, Languages and Programming
• scientific article; zbMATH DE number 7760193 (Why is no real title available?)
• Experimental and Efficient Algorithms
• A Lower Bound on Cycle-Finding in Sparse Digraphs
• Testing connectivity of faulty networks in sublinear time
• Lane covering with partner bounds in collaborative truckload transportation procurement
• A New Algorithm for Finding Minimal Cycle-Breaking Sets of Turns in a Graph
• Revised Greedy algorithm for formation of a minimal cycle basis of a graph
• Properties of Gomory-Hu co-cycle bases
• Characterization of minimum cycle basis in weighted partial 2-trees
• Rooted cycle bases
• Minimum cycle bases for network graphs
• Toward fast calculation of communication paths for resilient routing

This page was built for publication: Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs

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