Other formats:
BibTeX
LaTeX
RIS
@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.
|
