Edge-coloured directed graphs provide an essential structure for modelling and computing complex problems arising in many scientific disciplines. The size of edge-coloured graphs appearing in practice can be enormous in the number of both vertices and colours. An important fundamental problem that needs to be solved over edge-coloured graphs is detecting strongly connected components. The problem becomes challenging for large graphs with a large number of colours. In this paper, we describe a novel 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$ is 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.
翻译：彩色定向图形为建模和计算在许多科学学科中产生的复杂问题提供了基本结构。 实际中显示的边色图形的大小在脊椎和颜色的数量上都可能十分巨大。 需要通过边色图形解决的一个重要基本问题就是探测强烈关联的成分。 问题对于具有大量颜色的大型图形来说具有挑战性。 在本文中, 我们描述一种新型的象征性算法, 计算出边色图形中所有单色紧密相连的成分。 在最糟糕的情况下, 算法执行$O( p\cdot n\cdot\log n)$的象征性步骤, 其中, $p$是颜色的数量, $n美元是脊椎的数量。 我们使用基于二进制决定图(BDDDs)和大型图( $2 ⁇ 48}) 的实验性算法, 我们用系统生物学模型产生的彩色图表来评估算法。
相关内容
微信扫码咨询专知VIP会员