Product graph representations
Product graph representations
复制标题
产品图表表示
DOI：
10.1002/jgt.3190160508
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
T. Feder
中科院分区：
文献类型：
--
作者：
T. Feder
本文研究了图的卡图积的子图的一类正则表示。这个层次结构开始于等距表示，包括2-等距表示，并结束于卡氏素分解。我们表明，所有这三个表示可以在O（nm）的时间使用O（m）的空间，具有n个顶点和m条边的图。该算法有立即并行版本，使用n3处理器和运行在O（log 2n）的时间。© 1929 John Wiley & Sons，Inc.
We study a hierarchy of canonical representations of grpahs as subgraphs of cartesian products of graphs. This hierarchy starts with the isometric representation, includes the 2-isometric represnetation, and ends with the cartesian prime factorization. We show that all three representations can be obtained in O(nm) time using O(m) space, for graphs with n vertices and m edges. The algorithms have immediate parallel versions that use n3 processors and run in O(log2n) time. © 1929 John Wiley & Sons, Inc.