{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T05:21:25Z","timestamp":1672377685712},"reference-count":16,"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":"Circle graphs are an important class of graph with applications in a number of areas, including compiler optimization, VLSI design and computational geometry. In this article, we provide an experimental evaluation of the two most efficient algorithms for computing the maximum independent set of a circle graph. We provide details of our implementations of the algorithms of Apostolico et al. and Valiente [2003], together with time, space, and other measurements. We describe optimizations to the algorithm of Apostolico et al. that significantly reduce both its running time and its memory consumption. We also correct an error in this algorithm. In addition, we show how to restructure and simplify Valiente's algorithm, allowing us to remove redundant computations from the algorithm resulting in much improved performance. Moreover, in the case of both algorithms, when the density of the circle graph's associated interval representation is increased beyond a certain point the efficacy of the optimizations we apply increases dramatically and as a function of the density. We provide experimental results over dense and sparse random circle graphs, as well as for circle graphs that arise when performing register allocation of software pipelined loops in a compiler.<\/jats:p>","DOI":"10.1145\/1412228.1455265","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":3,"title":["Efficiently implementing maximum independent set algorithms on circle graphs"],"prefix":"10.1145","volume":"13","author":[{"given":"Nicholas","family":"Nash","sequence":"first","affiliation":[{"name":"Trinity College Dublin, Dublin, Ireland"}]},{"given":"Sylvain","family":"Lelait","sequence":"additional","affiliation":[{"name":"European Patent Office"}]},{"given":"David","family":"Gregg","sequence":"additional","affiliation":[{"name":"Trinity College Dublin, Dublin, Ireland"}]}],"member":"320","published-online":{"date-parts":[[2009,2,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90200-T"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90200-T"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/5383.5387"},{"key":"e_1_2_1_4_1","unstructured":"Asano T. Imai H. and Mukaiyama A. 1991. Finding a maximum weight independent set of a circle graph. IEICE Transactions E74 4 681--683. Asano T. Imai H. and Mukaiyama A. 1991. Finding a maximum weight independent set of a circle graph. IEICE Transactions E74 4 681--683."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.45872"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00105-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(01)00058-3"},{"key":"e_1_2_1_8_1","unstructured":"Eisenbeis C. Lelait S. and Marmol B. 1995. The meeting graph: a new model for loop cyclic register allocation. In PACT '95: Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques. IFIP Working Group on Algol Manchester UK 264--267. Eisenbeis C. Lelait S. and Marmol B. 1995. The meeting graph: a new model for loop cyclic register allocation. In PACT '95: Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques. IFIP Working Group on Algol Manchester UK 264--267."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030305"},{"key":"e_1_2_1_10_1","unstructured":"Goldschmidt O. and Takvorian A. 1994. An efficient algorithm for finding a maximum weight independent set of a circle graph. IEICE Transactions E77-A 10 1672--1674. Goldschmidt O. and Takvorian A. 1994. An efficient algorithm for finding a maximum weight independent set of a circle graph. IEICE Transactions E77-A 10 1672--1674."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120410"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90097-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189092"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90206-W"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1987.1270250"},{"key":"e_1_2_1_16_1","series-title":"Lecture Notes in Computer Science","volume-title":"A new simple algorithm for the maximum-weight independent set problem on circle graphs","author":"Valiente G."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412228.1455265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T08:55:12Z","timestamp":1672304112000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1455265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":16,"alternative-id":["10.1145\/1412228.1455265"],"URL":"http:\/\/dx.doi.org\/10.1145\/1412228.1455265","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]]}}}