A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation

DOI10.1002/net.20316zbMath1214.68259OpenAlexW4230860438MaRDI QIDQ3057155

Peter Morling, Marco Chiarandini, Jörgen Bang-Jensen

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20316

zbMATH Keywords

heuristicsaugmentationlocal searchset coveringedge-connectivitysurvivable networksvery large scale neighborhood

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Communication networks in operations research (90B18) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (3)

Robustness and Strong Attack Tolerance of Low-Diameter Networks ⋮ Topology design for on-demand dual-path routing in wireless networks ⋮ Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks

Uses Software

• SCIP
• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of very large-scale neighborhood search techniques
• Edge-connectivity augmentation problems
• A genetic algorithm for the set covering problem
• Polynomial time algorithms for 2-edge-connectivity augmentation problems
• Evolutionary local search for the edge-biconnectivity augmentation problem
• A note on finding the bridges of a graph
• Conflict analysis in mixed integer programming
• A 3-flip neighborhood local search for the set covering problem
• The minimum augmentation of any graph to aK-edge-connected graph
• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for Several Graph Augmentation Problems
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Approximation Algorithms for Graph Augmentation
• Augmentation Problems
• Edge-Connectivity Augmentation Preserving Simplicity
• A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering
• Strong formulations for network design problems with connectivity requirements
• A Heuristic Method for the Set Covering Problem
• A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems
• Design of Survivable Networks: A survey
• Collective dynamics of ‘small-world’ networks

This page was built for publication: A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation