Symbolic Coloured SCC Decomposition

D 2021

Symbolic Coloured SCC Decomposition

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

Základní údaje

Originální název

Symbolic Coloured SCC Decomposition

Autoři

BENEŠ, Nikola (203 Česká republika, domácí), Luboš BRIM (203 Česká republika, domácí), Samuel PASTVA (703 Slovensko, domácí) a David ŠAFRÁNEK (203 Česká republika, garant, domácí)

Vydání

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

Nakladatel

Springer Nature

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/21:00121404

Organizační jednotka

Fakulta informatiky

ISBN

978-3-030-72012-4

ISSN

DOI

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

Klíčová slova anglicky

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

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 15. 5. 2024 02:09, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.

Návaznosti

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

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

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace X.

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

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

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 21

Citovat

BENEŠ, Nikola, Luboš BRIM, Samuel PASTVA a 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, s. 64-83. ISBN 978-3-030-72012-4. Dostupné z: 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 a 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, s.~64-83. ISBN~978-3-030-72012-4. Dostupné z: https://dx.doi.org/10.1007/978-3-030-72013-1\_{}4.

Podrobný výpis o publikaci