An algorithm forK-convex closure and an application
Tomaž Pisanski, Blaž Zmazek, Janez �erovnik · International Journal of Computer Mathematics · 2001
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.