Symbolic Coloured SCC Decomposition
| Authors | |
|---|---|
| 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 | |
| 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: |