An algorithm for K-convex closure and an application
An algorithm for K-convex closure and an application
复制标题
一种K-凸闭包算法及应用
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
J. Žerovnik
中科院分区：
文献类型：
--
作者：
T. Pisanski;B. Zmazek;J. Žerovnik
给出了计算相对于图的边之间给定等价关系 R 的子图的 K 凸闭包的算法。对于一般图和任意关系 R，时间复杂度为 O(q n 2 + mn)，其中 n 是顶点数，m 是边数，q 是 R 的等价类数。特殊情况是通常 k 凸性的 O(mn) 算法。我们还表明，笛卡尔图束在三角形自由上可以在 O(mn) 时间内识别碱基，并且可以在 O(mn 2) 时间内找到诸如笛卡尔图束之类的图的所有表示。
An algorithm for computing the K-convex closure of a subgraph relative to a given equivalence relation R among edges of a graph is given.For general graph and arbitrary relation R the time complexity is O(q n 2 + mn), where n is the number of vertices, m is the number of edges and q is the number of equivalence classes of R.A special case is an O(mn) algorithm for the usual k-convexity.We also show that Cartesian graph bundles over triangle free bases can be recognized in O(mn) time and that all representations of such graphs as Cartesian graph bundles can be found in O(mn 2) time.