A greedy approach to compute a minimum cycle basis of a directed graph

DOI10.1016/j.ipl.2005.01.006zbMath1189.68085OpenAlexW2005869405MaRDI QIDQ1041731

Christian Liebchen, Romeo Rizzi

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.01.006

zbMATH Keywords

greedy algorithmgraph algorithmsdirected graphsminimum cycle bases

Mathematics Subject Classification ID

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

Related Items

Cycle analysis of directed acyclic graphs ⋮ Classes of cycle bases ⋮ Cycle-based formulations in distance geometry ⋮ On a Special Co-cycle Basis of Graphs ⋮ New approximation algorithms for minimum cycle bases of graphs ⋮ Integrating Passengers' Routes in Periodic Timetabling: A SAT approach. ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ Integral cycle bases for cyclic timetabling ⋮ A cycle-based formulation for the distance geometry problem ⋮ Minimum Cycle Bases and Their Applications ⋮ Minimum weakly fundamental cycle bases are hard to find ⋮ Properties of Gomory-Hu co-cycle bases ⋮ A greedy approach to compute a minimum cycle basis of a directed graph ⋮ An efficient algorithm for 1-dimensional (Persistent) path homology ⋮ Minimum cycle bases of graphs over different fields

Cites Work

• Unnamed Item
• Unnamed Item
• Integral cycle bases for cyclic timetabling
• A greedy approach to compute a minimum cycle basis of a directed graph
• Minimum cycle bases for network graphs
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Automata, Languages and Programming
• Approximation and Online Algorithms
• Algorithms - ESA 2003