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 | BENEŠ, Nikola; Luboš BRIM; Samuel PASTVA and David ŠAFRÁNEK. Symbolic Coloured SCC Decomposition. Online. In Jan Friso Groote, Kim Larsen. Tools and Algorithms for the Construction and Analysis of Systems, 27th International Conference, TACAS 2021. Neuveden: Springer Nature, 2021, p. 64-83. ISBN 978-3-030-72012-4. Available from: https://dx.doi.org/10.1007/978-3-030-72013-1_4. |
| 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: |