An algorithm for K-convex closure and an application

Abstract

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 ² + 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 ²) time.

Keywords:

• Graph
• Convex closure
• Graph bundle
• Recognition algorithm

C.R. Categories:

• F.2.2
• G.2.2

^* [email protected]

^† [email protected]

^* [email protected]

^† [email protected]

Notes

^* [email protected]

^† [email protected]