# Masarykova univerzita

Informace o publikaci

# Symbolic Coloured SCC Decomposition

Autoři 2021 Článek ve sborníku Tools and Algorithms for the Construction and Analysis of Systems, 27th International Conference, TACAS 2021 https://doi.org/10.1007/978-3-030-72013-1_4 http://dx.doi.org/10.1007/978-3-030-72013-1_4 strongly connected components; symbolic algorithm; edge-coloured digraphs; systems biology 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.

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.