On the approximability of the minimum strictly fundamental cycle basis problem

DOI10.1016/j.dam.2010.10.014zbMath1210.05067OpenAlexW2014313757MaRDI QIDQ629358

Edoardo Amaldi, Giulia Galbiati, Romeo Rizzi

Publication date: 9 March 2011

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

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

zbMATH Keywords

approximation algorithmpolynomial-time approximation schememinimum cycle basisstrictly fundamental cycle basis

Mathematics Subject Classification ID

Paths and cycles (05C38)

Related Items (5)

Minimum strictly fundamental cycle bases of planar graphs are hard to find ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ Minimum cut bases in undirected networks ⋮ Edge-swapping algorithms for the minimum fundamental cycle basis problem ⋮ On minimum average stretch spanning trees in polygonal 2-trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classes of cycle bases
• Integral cycle bases for cyclic timetabling
• Some APX-completeness results for cubic graphs
• On cycle bases of a graph
• Optimum Communication Spanning Trees
• Lower-stretch spanning trees
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Algorithms for Generating Fundamental Cycles in a Graph
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Approximation and Online Algorithms

This page was built for publication: On the approximability of the minimum strictly fundamental cycle basis problem