Symbolic Coloured SCC Decomposition

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

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

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

Fakulta informatiky

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:

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