Symbolic Coloured SCC Decomposition

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BENEŠ Nikola BRIM Luboš PASTVA Samuel ŠAFRÁNEK David

Year of publication 2021
Type Article in Proceedings
Conference Tools and Algorithms for the Construction and Analysis of Systems, 27th International Conference, TACAS 2021
MU Faculty or unit

Faculty of Informatics

Citation
Web https://doi.org/10.1007/978-3-030-72013-1_4
Doi http://dx.doi.org/10.1007/978-3-030-72013-1_4
Keywords strongly connected components; symbolic algorithm; edge-coloured digraphs; systems biology
Description Problems arising in many scientific disciplines are often modelled using edge-coloured directed graphs. These can be enormous in the number of both vertices and colours. Given such a graph, the original problem frequently translates to the detection of the graph's strongly connected components, which is challenging at this scale. We propose a new, symbolic algorithm that computes all the monochromatic strongly connected components of an edge-coloured graph. In the worst case, the algorithm performs $O(p\cdot n\cdot\log n)$ symbolic steps, where $p$ is the number of colours and $n$ the number of vertices. We evaluate the algorithm using an experimental implementation based on Binary Decision Diagrams (BDDs) and large (up to $2^{48}$) coloured graphs produced by models appearing in systems biology.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.