Classes of cycle bases

DOI10.1016/j.dam.2006.06.007zbMath1147.05043OpenAlexW2126496074MaRDI QIDQ868389

Romeo Rizzi, Christian Liebchen

Publication date: 2 March 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.06.007

zbMATH Keywords

combinatorial optimizationgraphsminimum cycle basis problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Paths and cycles (05C38)

Related Items

A characterization of circle graphs in terms of total unimodularity ⋮ Cycle analysis of directed acyclic graphs ⋮ Minimum spanning tree cycle intersection problem ⋮ Minimum cycle bases of weighted outerplanar graphs ⋮ On the approximability of the minimum strictly fundamental cycle basis problem ⋮ Forward and line-based cycle bases for periodic timetabling ⋮ On a Special Co-cycle Basis of Graphs ⋮ On quiver representations over \(\mathbb{F}_1\) ⋮ Minimum spanning tree cycle intersection problem on outerplanar graphs ⋮ New approximation algorithms for minimum cycle bases of graphs ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ Minimum fundamental cycle basis of some bipartite graphs ⋮ Minimum cycle basis of direct product of \(K_2 \times K_n\) ⋮ Lower bounds for strictly fundamental cycle bases in grid graphs ⋮ Periodic railway timetabling with event flexibility ⋮ Integral cycle bases for cyclic timetabling ⋮ Minimum Cycle Bases and Their Applications ⋮ Minimum weakly fundamental cycle bases are hard to find ⋮ A note on fundamental, non-fundamental, and robust cycle bases ⋮ Properties of Gomory-Hu co-cycle bases ⋮ Cyclic matrices of weighted digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Integral cycle bases for cyclic timetabling
• A greedy approach to compute a minimum cycle basis of a directed graph
• On the null-homotopy of graphs
• Planar graphs: Theory and algorithms
• Minimal cycle bases of outerplanar graphs
• Minimum cycle bases for network graphs
• On cycle bases of a graph
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Algorithms for Generating Fundamental Cycles in a Graph
• Efficient Planarity Testing
• Automata, Languages and Programming
• STACS 2005
• Approximation and Online Algorithms
• Algorithms - ESA 2003
• Tree spanners in planar graphs