Symbolic Coloured SCC Decomposition
| Autoři | |
|---|---|
| Rok publikování | 2021 |
| Druh | Článek ve sborníku |
| Konference | Tools and Algorithms for the Construction and Analysis of Systems, 27th International Conference, TACAS 2021 |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://doi.org/10.1007/978-3-030-72013-1_4 |
| Doi | http://dx.doi.org/10.1007/978-3-030-72013-1_4 |
| Klíčová slova | strongly connected components; symbolic algorithm; edge-coloured digraphs; systems biology |
| Popis | 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. |
| Související projekty: |