On the approximability of the minimum strictly fundamental cycle basis problem

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

Romeo Rizzi, Edoardo Amaldi, Giulia Galbiati

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 algorithm; polynomial-time approximation scheme; minimum cycle basis; strictly fundamental cycle basis

Mathematics Subject Classification ID

05C38: Paths and cycles

Related Items

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