On the approximability of the minimum strictly fundamental cycle basis problem

DOI10.1016/J.DAM.2010.10.014MaRDI QIDQ629358zbMATH OpenOpenAlexFDO

Authors Giulia Galbiati, Romeo Rizzi, E. Amaldi

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 algorithmminimum cycle basispolynomial-time approximation schemestrictly fundamental cycle basis

Mathematics Subject Classification ID

Paths and cycles (05C38)

Recommendations

• Approximation and Online Algorithms
• New Approximation Algorithms for Minimum Cycle Bases of Graphs
• New approximation algorithms for minimum cycle bases of graphs
• Algorithms for finding minimum fundamental cycle bases in graphs
• Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases
• Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs
• Minimum Cycle Bases and Their Applications
• An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs
• Minimum Cycle Bases in Graphs Algorithms and Applications
• On finding cycle bases and fundamental cycle bases with a shortest maximal cycle

Cites work

• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Algorithms for Generating Fundamental Cycles in a Graph
• Approximation and Online Algorithms
• Classes of cycle bases
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1145916 (Why is no real title available?)
• scientific article; zbMATH DE number 2080984 (Why is no real title available?)
• Integral cycle bases for cyclic timetabling
• Lower-stretch spanning trees
• On cycle bases of a graph
• Optimum Communication Spanning Trees
• Some APX-completeness results for cubic graphs

Cited in

(13)

• Edge-swapping algorithms for the minimum fundamental cycle basis problem
• Minimum weakly fundamental cycle bases are hard to find
• On finding cycle bases and fundamental cycle bases with a shortest maximal cycle
• On minimum average stretch spanning trees in polygonal 2-trees
• New length bounds for cycle bases
• Minimum strictly fundamental cycle bases of planar graphs are hard to find
• scientific article; zbMATH DE number 558500 (Why is no real title available?)
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices
• Lower bounds for strictly fundamental cycle bases in grid graphs
• Benchmarks for Strictly Fundamental Cycle Bases
• Approximation and Online Algorithms
• Minimum cut bases in undirected networks

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

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