Combinatorial optimization in networks with Shared Risk Link Groups
This page provides a program implementing methods presented in [CPRV16]
for solving the minimum color st-path, the pair of color disjoint st-paths and the
minimum color st-cut problems in (multi-)colored graphs. It also implements algorithms
to transform a multi-colored graph into a mono-color graph with as few colors of span>1 as
The program is provided 'as is', with absolutely no warranty. It is written in Python and Cython to be used with the open-source mathematical software SageMath. It has been developped and used with Sagemath version 6.8 (stable release).
You may use and distribute this code, provided that you cite the paper describing our algorithms, [CPRV16]. Please let us know if you find the program useful, if you find a bug, or have any improvement.
- Program: the SRLG.zip archive contains a README file, the Python/Cython source code, and a set of colored-graphs.
- [CPRV16] David Coudert, Stéphane Pérennes, Hervé Rivano, Marie-Emilie Voge. Combinatorial optimization in networks with Shared Risk Link Groups. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 18, no 3, pp.25.