### An improved heuristic for computing short integral cycle basesAn improved heuristic for computing short integral cycle bases

Access Restriction
Subscribed

 Author Kavitha, Telikepalli ♦ Krishna, Katakam Vamsi Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Directed graph ♦ Combinatorial optimization ♦ Integral cycle basis ♦ Minimum cycle basis Abstract In this article, we consider the problem of constructing low-weight integral cycle bases in a directed graph $\textit{G}$ = $(\textit{V},$ $\textit{E})$ with nonnegative edge weights. It has been shown that low-weight integral cycle bases have applications in the periodic event scheduling problem and cyclic time tabling. However, no polynomial time algorithm is known for computing a minimum weight integral cycle basis in a given directed graph. We give a necessary condition that has to be satisfied by any minimum weight integral cycle basis and guided by this necessary condition, we propose a new heuristic for constructing a low weight integral cycle basis. To the best of our knowledge, this is the first algorithm to construct integral cycle bases that are not necessarily fundamental. We implemented our heuristic and tested it on random graphs and compared the weight of the integral cycle basis computed by our algorithm with the weight of a minimum cycle basis and the weights of integral cycle bases (these are, in fact, fundamental cycle bases) computed by already existing and new heuristics for this problem. Empirical results suggest that our heuristic performs better than the existing heuristics for this problem and in fact, it computes a $\textit{minimum}$ weight integral cycle basis on these graphs. (In the above comparison, when the weight of the integral cycle basis computed and the weight of a minimum cycle basis turn out to be equal, it immediately implies that we have in fact found a minimum integral cycle basis.) The time needed for our heuristic is typically a little higher compared to the time taken by the other heuristics that compute fundamental cycle bases. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-02-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 13 Page Count 10 Starting Page 1.14 Ending Page 1.23

#### Open content in new tab

Source: ACM Digital Library