Minimum Cycle Bases and Their Applications

DOI10.1007/978-3-642-02094-0_2MaRDI QIDQ3637310zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Franziska Berger, Peter Gritzmann, Sven De Vries

Publication date 9 July 2009

Published in Algorithmics of Large and Complex Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02094-0_2

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Minimum Cycle Bases in Graphs Algorithms and Applications
• Minimum cycle bases, faster and simpler
• Algorithms to compute minimum cycle basis in directed graphs
• An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs
• Faster Algorithms for Minimum Cycle Basis in Directed Graphs

Cites work

• A greedy approach to compute a minimum cycle basis of a directed graph
• A Mathematical Model for Periodic Scheduling Problems
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Algorithms for finding minimum fundamental cycle bases in graphs
• Algorithms for Generating Fundamental Cycles in a Graph
• Algorithms to compute minimum cycle basis in directed graphs
• An algorithm for finding a fundamental set of cycles of a graph
• Approximation and Online Algorithms
• Automata, Languages and Programming
• Classes of cycle bases
• Faster Algorithms for Minimum Cycle Basis in Directed Graphs
• Finding short integral cycle bases for cyclic timetabling
• scientific article; zbMATH DE number 2089223 (Why is no real title available?)
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 5343212 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 2065115 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• Interchangeability of relevant cycles in graphs
• Is every cycle basis fundamental?
• Minimizing waiting times in integrated fixed interval timetables by upgrading railway tracks
• Minimum cycle bases for network graphs
• Minimum cycle bases of graphs over different fields
• Minimum cycle bases, faster and simpler
• Minimum weakly fundamental cycle bases are hard to find
• New Approximation Algorithms for Minimum Cycle Bases of Graphs
• New length bounds for cycle bases
• Performance of algorithms for periodic timetable optimization
• Periodic network optimization with different arc frequencies
• The prism-free planar graphs and their cycles bases
• Union of all the minimum cycle bases of a graph
• When do short cycles generate the cycle space?

Cited in

(26)

• Minimum weakly fundamental cycle bases are hard to find
• Cycle bases from orderings and coverings
• Union of all the minimum cycle bases of a graph
• Minimum cycle bases of weighted outerplanar graphs
• Interchangeability of relevant cycles in graphs
• The lattice of cycles of an undirected graph
• Algorithms to compute minimum cycle basis in directed graphs
• On minimal circuits for linear functions over some bases
• Minimum Path Bases
• Convex cycle bases
• Minimum path bases and relevant paths
• Rooted cycle bases
• On a Special Co-cycle Basis of Graphs
• Minimum Cycle Bases in Graphs Algorithms and Applications
• Minimum cycle bases of weighted outerplanar graphs
• scientific article; zbMATH DE number 2080984 (Why is no real title available?)
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Circuit bases of strongly connected digraphs
• Rooted cycle bases
• An improved heuristic for computing short integral cycle bases
• The minimal cycle basis of circular graphs
• On the approximability of the minimum strictly fundamental cycle basis problem
• Computing cyclic invariants for molecular graphs
• When do short cycles generate the cycle space?
• Properties of Gomory-Hu co-cycle bases
• Classes of cycle bases

Describes a project that uses

Uses Software

• PESPLib

This page was built for publication: Minimum Cycle Bases and Their Applications

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