Symbolic Coloured SCC Decomposition

D 2021

Symbolic Coloured SCC Decomposition

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

Basic information

Original name

Symbolic Coloured SCC Decomposition

Authors

BENEŠ, Nikola (203 Czech Republic, belonging to the institution), Luboš BRIM (203 Czech Republic, belonging to the institution), Samuel PASTVA (703 Slovakia, belonging to the institution) and David ŠAFRÁNEK (203 Czech Republic, guarantor, belonging to the institution)

Edition

Neuveden, Tools and Algorithms for the Construction and Analysis of Systems, 27th International Conference, TACAS 2021, p. 64-83, 20 pp. 2021

Publisher

Springer Nature

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Switzerland

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

URL

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/21:00121404

Organization unit

Faculty of Informatics

ISBN

978-3-030-72012-4

ISSN

DOI

http://dx.doi.org/10.1007/978-3-030-72013-1_4

Keywords in English

strongly connected components; symbolic algorithm; edge-coloured digraphs; systems biology

Abstract

V originále

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.

Links

MUNI/A/1108/2020, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X. (Acronym: SV-FI MAV X.)

Investor: Masaryk University

MUNI/A/1549/2020, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21 (Acronym: SKOMU)

Investor: Masaryk University

Citovat

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.

@inproceedings{1759896,
   author = {Beneš, Nikola and Brim, Luboš and Pastva, Samuel and Šafránek, David},
   address = {Neuveden},
   booktitle = {Tools and Algorithms for the Construction and Analysis of Systems, 27th International Conference, TACAS 2021},
   doi = {http://dx.doi.org/10.1007/978-3-030-72013-1_4},
   editor = {Jan Friso Groote, Kim Larsen},
   keywords = {strongly connected components; symbolic algorithm; edge-coloured digraphs; systems biology},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Neuveden},
   isbn = {978-3-030-72012-4},
   pages = {64-83},
   publisher = {Springer Nature},
   title = {Symbolic Coloured SCC Decomposition},
   url = {https://doi.org/10.1007/978-3-030-72013-1_4},
   year = {2021}
}

TY  - JOUR
ID  - 1759896
AU  - Beneš, Nikola - Brim, Luboš - Pastva, Samuel - Šafránek, David
PY  - 2021
TI  - Symbolic Coloured SCC Decomposition
PB  - Springer Nature
CY  - Neuveden
SN  - 9783030720124
KW  - strongly connected components
KW  - symbolic algorithm
KW  - edge-coloured digraphs
KW  - systems biology
UR  - https://doi.org/10.1007/978-3-030-72013-1_4
N2  - 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.
ER  -

BENEŠ, Nikola, Luboš BRIM, Samuel PASTVA and David ŠAFRÁNEK. Symbolic Coloured SCC Decomposition. Online. In Jan Friso Groote, Kim Larsen. \textit{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.

Detailed Information on Publication Record