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.
|