| A Faster Deterministic Algorithm for Minimum Cycle Basis in Directed Graphs (2008) | |||||||||||||||
Abstract | |||||||||||||||
| We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is actually a cycle in the underlying undirected graph with edges traversable in both directions. A f1;0;1g edge incidence vector is associated with each cycle: edges traversed by the cycle in the right direction get 1 and edges traversed in the opposite direction get-1. The vector space over Q generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for this vector space. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||