Fractional routing using pairs of failure-disjoint paths

DOI10.1016/J.DAM.2011.12.019MaRDI QIDQ496701zbMATHOpenAlexFDO

Authors Walid Ben-Ameur, Michał Pióro, Mateusz Żotkiewicz

Publication date 22 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.12.019

zbMATH Keywords

shortest pathscolumn generationdisjoint pathscapacitated network designcompact formulations

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Reliability, availability, maintenance, inspection in operations research (90B25) Stochastic network models in operations research (90B15)

Recommendations

• The fractional congestion bound for efficient edge disjoint routing
• Disjoint-paths and fault-tolerant routing on recursive dual-net
• Routing in hypercube networks with a constant fraction of faulty nodes
• Distributed routing in a fault-tolerant multistage interconnection network
• Fault-tolerant routings in double fixed-step networks
• Optimal routing with failure-independent path protection
• Probability-based fault-tolerant routing in hypercubes
• Fault-tolerant routing in hypercubes using probability vectors

Cites work

• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 2150800 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• scientific article; zbMATH DE number 961880 (Why is no real title available?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A quick method for finding shortest pairs of disjoint paths
• Design of Survivable Networks: A survey
• Emergence of Scaling in Random Networks
• Linear approximations in a dynamic programming approach for the uncapacitated single-source minimum concave cost network flow problem in acyclic networks.
• Network flows. Theory, algorithms, and applications.
• On multiroute maximum flows in networks.
• On the minimum cost multiple-source unsplittable flow problem

Cited in

(3)

• Failure disjoint paths
• Optimal routing with failure-independent path protection
• Branch-and-price-and-cut algorithms for solving the reliable \(h\)-paths problem

Describes a project that uses

Uses Software

• SNDlib
• CPLEX

This page was built for publication: Fractional routing using pairs of failure-disjoint paths

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