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

DOI10.1007/978-3-642-13036-6_30zbMATH Open1284.05261OpenAlexW1605294700MaRDI QIDQ3569834FDOQ3569834

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

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

Mathematics Subject Classification ID

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

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
• An efficient algorithm for searching implicit AND/OR graphs with cycles
• On the approximability of the minimum strictly fundamental cycle basis problem
• New approximation algorithms for minimum cycle bases of graphs
• Automata, Languages and Programming
• Title not available (Why is that?)
• 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
• Rooted cycle bases
• Characterization of minimum cycle basis in weighted partial 2-trees
• Toward fast calculation of communication paths for resilient routing
• Minimum cycle bases for network graphs

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)