Edge-swapping algorithms for the minimum fundamental cycle basis problem

DOI10.1007/s00186-008-0255-4zbMath1163.90036OpenAlexW2140109884MaRDI QIDQ1014301

Edoardo Amaldi, Leo Liberti, Francesco Maffioli, Nelson F. Maculan

Publication date: 27 April 2009

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00186-008-0255-4

zbMATH Keywords

fundamental cycleheuristicmetaheuristiccycle basisedge swapfundamental cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

A matroid view of key theorems for edge-swapping algorithms, Distance geometry and data science, Cycle-based formulations in distance geometry, Minimum cut bases in undirected networks, Variable neighbourhood search: methods and applications, A cycle-based formulation for the distance geometry problem

Uses Software

• LEDA
• CPLEX
• PESPLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the approximability of the minimum strictly fundamental cycle basis problem
• New length bounds for cycle bases
• On cycle bases of a graph
• On the fundamental cycle set graph
• Algorithms for finding minimum fundamental cycle bases in graphs
• Is every cycle basis fundamental?
• Lower-stretch spanning trees
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• A Mathematical Model for Periodic Scheduling Problems
• Algorithms for Generating Fundamental Cycles in a Graph
• Finding All Spanning Trees of Directed and Undirected Graphs
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
• Exact algorithms for minimum routing cost trees
• Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• Benchmarks for Strictly Fundamental Cycle Bases
• Automata, Languages and Programming
• An algorithm for finding a fundamental set of cycles of a graph
• Algorithms - ESA 2003
• Variable neighborhood search: Principles and applications