b'@inproceedings{HTM06a,'b'\nTITLE = {A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs},\nAUTHOR = {Hariharan, Ramesh and Telikepalli, Kavitha and Mehlhorn, Kurt},\nEDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimir and Wegener, Ingo},\nLANGUAGE = {eng},\nISBN = {3-540-35904-4},\nLOCALID = {Local-ID: C1256428004B93B8-C5345CC3A9361E5BC12571CA003B984B-HTM06a},\nPUBLISHER = {Springer},\nYEAR = {2006},\nDATE = {2006},\nABSTRACT = {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 {--1,0,1} 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 generated by these vectors is the cycle space of G. A minimum cycle basis is a set of cycles of minimum weight that span the cycle space of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m edges and n vertices runs in time (where $\\omega$< 2.376 is the exponent of matrix multiplication). Here we present an O(m3n + m2n2logn) algorithm. We also slightly improve the running time of the current fastest randomized algorithm from O(m2nlogn) to O(m2 n + mn2 logn).},\nBOOKTITLE = {Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Part I},\nPAGES = {250--261},\nSERIES = {Lecture Notes in Computer Science},\nVOLUME = {4051},\n}\n'