Nicholas Nash
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.
- Apostolico, A., Atallah, M. J., and Hambrusch, S. E. 1992. New clique and independent set algorithms for circle graphs. Discrete Applied Mathematics 36, 1, 1--24. Google Scholar
Digital Library
- Apostolico, A., Atallah, M. J., and Hambrusch, S. E. 1993. Erratum: New clique and independent set algorithms for circle graphs (discrete applied mathematics 36 (1992) 1--24). Discrete Applied Mathematics 41, 2, 179--180. Google ScholarDigital Library
- Asano, T., Asano, T., and Imai, H. 1986. Partitioning a polygonal region into trapezoids. J. ACM 33, 2, 290--312. Google ScholarDigital Library
- Asano, T., Imai, H., and Mukaiyama, A. 1991. Finding a maximum weight independent set of a circle graph. IEICE Transactions E74, 4, 681--683.Google Scholar
- Cong, J. and Liu, C. L. 1990. Over-the-cell channel routing. IEEE Trans. on CAD of Integrated Circuits and Systems 9, 4, 408--418.Google ScholarCross Ref
- de Werra, D., Eisenbeis, C., Lelait, S., and Marmol, B. 1999. On a graph-theoretical model for cyclic register allocation. Discrete Applied Mathematics 93, 2-3, 191--203. Google ScholarDigital Library
- de Werra, D., Eisenbeis, C., Lelait, S., and Stöhr, E. 2002. Circular-arc graph coloring: on chords and circuits in the meeting graph. European Journal of Oper. Research 136, 483--500.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Gavril, F. 1973. Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3, 3, 261--273.Google ScholarCross Ref
- 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.Google Scholar
- Gupta, U. I., Lee, D. T., and Leung, J. Y.-T. 1982. Efficient algorithms for interval graphs and circular-arc graphs. Networks 12, 4, 459--467.Google ScholarCross Ref
- Liu, R. and Ntafos, S. C. 1988. On decomposing polygons into uniformly monotone parts. Inf. Process. Lett. 27, 2, 85--89. Google ScholarDigital Library
- Scheinerman, E. R. 1988. Random interval graphs. Combinatorica 8, 4, 357--371.Google ScholarCross Ref
- Scheinerman, E. R. 1990. An evolution of interval graphs. Discrete Math. 82, 3, 287--302. Google ScholarDigital Library
- Supowit, K. J. 1987. Finding a maximum planar subset of a set of nets in a channel. IEEE Trans. on CAD of Integrated Circuits and Systems 6, 1, 93--94.Google ScholarDigital Library
- Valiente, G. 2003. A new simple algorithm for the maximum-weight independent set problem on circle graphs. In ISAAC, T. Ibaraki, N. Katoh, and H. Ono, Eds. Lecture Notes in Computer Science, vol. 2906. Springer, 129--137.Google Scholar
Index Terms
- Efficiently implementing maximum independent set algorithms on circle graphs
Recommendations
Maximum induced multicliques and complete multipartite subgraphs in polygon-circle graphs and circle graphs
WG'12: Proceedings of the 38th international conference on Graph-Theoretic Concepts in Computer ScienceA graph is a multiclique if its connected components are cliques. A graph is a complete multipartite graph if it is the complement of a multiclique. A graph is a multiclique-multipartite graph if its vertex set has a partition U, W such that G(U) is ...
An output sensitive algorithm for computing a maximum independent set of a circle graph
We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(nmin{d,@a}) time at worst, for an n vertex circle graph where @a is the independence number of the circle graph and ...
The Maximum Independent Set Problem in Subclasses of Subcubic Graphs
The Maximum Independent Set problem is NP-hard and remains NP-hard for graphs of maximum degree at most three (also called subcubic graphs). In this paper, we will study its complexity in subclasses of subcubic graphs.Let S i , j , k be the graph ...
Comments