BDD-Based Algorithm for SCC Decomposition of Edge-Coloured Graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F22%3A00125612" target="_blank" >RIV/00216224:14330/22:00125612 - isvavai.cz</a>

Result on the web

<a href="https://lmcs.episciences.org/9198" target="_blank" >https://lmcs.episciences.org/9198</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.46298/LMCS-18(1:38)2022" target="_blank" >10.46298/LMCS-18(1:38)2022</a>

Result language

angličtina

Original language name

BDD-Based Algorithm for SCC Decomposition of Edge-Coloured Graphs

Original language description

Edge-coloured directed graphs provide an essential structure for modelling and analysis of complex systems arising in many scientific disciplines (e.g. feature-oriented systems, gene regulatory networks, etc.). One of the fundamental problems for edge-coloured graphs is the detection of strongly connected components, or SCCs. The size of edge-coloured graphs appearing in practice can be enormous both in the number of vertices and colours. The large number of vertices prevents us from analysing such graphs using explicit SCC detection algorithms, such as Tarjan's, which motivates the use of a symbolic approach. However, the large number of colours also renders existing symbolic SCC detection algorithms impractical. This paper proposes a novel algorithm that symbolically computes all the monochromatic strongly connected components of an edge-coloured graph. In the worst case, the algorithm performs O(p . n . log n) symbolic steps, where p is the number of colours and n is the number of vertices. We evaluate the algorithm using an experimental implementation based on binary decision diagrams (BDDs). Specifically, we use our implementation to explore the SCCs of a large collection of coloured graphs (up to 2(48)) obtained from Boolean networks - a modelling framework commonly appearing in systems biology.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

—

Volume of the periodical

18

Issue of the periodical within the volume

1

Country of publishing house

DE - GERMANY

Number of pages

27

Pages from-to

1-27

UT code for WoS article

000769134500001

EID of the result in the Scopus database

2-s2.0-85127140284