{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T05:19:59Z","timestamp":1672377599722},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,2]]},"abstract":"\n In this article, we consider the problem of constructing low-weight integral cycle bases in a directed graph\n G<\/jats:italic>\n = (\n V<\/jats:italic>\n ,\n E<\/jats:italic>\n ) 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.\n <\/jats:p>\n \n 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\n minimum<\/jats:italic>\n 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.\n <\/jats:p>","DOI":"10.1145\/1412228.1498696","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":1,"title":["An improved heuristic for computing short integral cycle bases"],"prefix":"10.1145","volume":"13","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}]},{"given":"Katakam Vamsi","family":"Krishna","sequence":"additional","affiliation":[{"name":"Google"}]}],"member":"320","published-online":{"date-parts":[[2009,2,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Lecture on the Annual Meeting of the DMV","author":"Berger F.","year":"2002","unstructured":"Berger , F. 2002 . Minimale kreisbasen in graphen . In Proceedings of the Lecture on the Annual Meeting of the DMV . Halle, Germany. Berger, F. 2002. Minimale kreisbasen in graphen. In Proceedings of the Lecture on the Annual Meeting of the DMV. Halle, Germany."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1098-x"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1976.0095"},{"key":"e_1_2_1_5_1","volume-title":"Graph Theory with Applications to Engineering and Computer Science","author":"Deo N.","unstructured":"Deo , N. 1982. Graph Theory with Applications to Engineering and Computer Science . Prentice-Hall , Englewood Cliffs, NJ . Deo, N. 1982. Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall, Englewood Cliffs, NJ."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 8th Scandinavian Workshop on Algorithm Theory.","author":"Golynski A.","unstructured":"Golynski , A. and Horton , J. D . 2002. A polynomial time algorithm to find the minimum cycle basis of a regular matroid . In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory. Golynski, A. and Horton, J. D. 2002. A polynomial time algorithm to find the minimum cycle basis of a regular matroid. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_23"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216026"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1319-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_71"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_64"},{"key":"e_1_2_1_13_1","volume-title":"Technical Report 761\/2002.","author":"Liebchen C.","year":"2002","unstructured":"Liebchen , C. and Peeters , L . 2002 . On cyclic timetabling and cycles in graphs. Tech. rep., TU Berlin . Technical Report 761\/2002. Liebchen, C. and Peeters, L. 2002. On cyclic timetabling and cycles in graphs. Tech. rep., TU Berlin. Technical Report 761\/2002."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.01.006"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.06.007"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644023"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1216582"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118778.3119189"},{"key":"e_1_2_1_20_1","unstructured":"Swamy M. and Thulasiraman K. 1981. Graphs Networks and Algorithms. John Wiley & Sons New York. Swamy M. and Thulasiraman K. 1981. Graphs Networks and Algorithms. John Wiley & Sons New York."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2006.08.019"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412228.1498696","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T08:54:00Z","timestamp":1672304040000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1498696"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":18,"alternative-id":["10.1145\/1412228.1498696"],"URL":"http:\/\/dx.doi.org\/10.1145\/1412228.1498696","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[2009,2]]}}}