Finding edge-disjoint paths in networks: an ant colony optimization algorithm

DOI10.1007/s10852-007-9060-yzbMath1149.90031OpenAlexW2067761491MaRDI QIDQ2466394

Christian Blum, Maria J. Blesa

Publication date: 14 January 2008

Published in: JMMA. Journal of Mathematical Modelling and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10852-007-9060-y

zbMATH Keywords

ant colony optimizationmaximum edge-disjoint paths problem

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (4)

Solving routing and wavelength assignment problem with maximum edge-disjoint paths ⋮ Solving the edge‐disjoint paths problem using a two‐stage method ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ Solving the maximum edge disjoint path problem using a modified Lagrangian particle swarm optimisation hybrid

Uses Software

• AntNet
• AntHocNet

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• An overtraining-resistant stochastic modeling method for pattern recognition
• Approximating disjoint-path problems using packing integer programs
• A linear time algorithm for the arc disjoint Menger problem in planar directed graphs
• Eulerian disjoint paths problem in grid graphs is NP-complete
• Simple on-line algorithms for the maximum disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints
• On the complexity of the disjoint paths problem
• Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
• Efficient routing in all-optical networks
• Emergence of Scaling in Random Networks
• Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
• Proof verification and the hardness of approximation problems
• The Vertex-Disjoint Menger Problem in Planar Graphs
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• The edge-disjoint paths problem is NP-complete for series-parallel graphs

This page was built for publication: Finding edge-disjoint paths in networks: an ant colony optimization algorithm