[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Efficiently implementing maximum independent set algorithms on circle graphs

Published: 23 February 2009 Publication History

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.

References

[1]
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.
[2]
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.
[3]
Asano, T., Asano, T., and Imai, H. 1986. Partitioning a polygonal region into trapezoids. J. ACM 33, 2, 290--312.
[4]
Asano, T., Imai, H., and Mukaiyama, A. 1991. Finding a maximum weight independent set of a circle graph. IEICE Transactions E74, 4, 681--683.
[5]
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.
[6]
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.
[7]
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.
[8]
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.
[9]
Gavril, F. 1973. Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3, 3, 261--273.
[10]
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.
[11]
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.
[12]
Liu, R. and Ntafos, S. C. 1988. On decomposing polygons into uniformly monotone parts. Inf. Process. Lett. 27, 2, 85--89.
[13]
Scheinerman, E. R. 1988. Random interval graphs. Combinatorica 8, 4, 357--371.
[14]
Scheinerman, E. R. 1990. An evolution of interval graphs. Discrete Math. 82, 3, 287--302.
[15]
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.
[16]
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.

Cited By

View all
  • (2019)An output sensitive algorithm for computing a maximum independent set of a circle graphInformation Processing Letters10.1016/j.ipl.2010.05.016110:16(630-634)Online publication date: 6-Jan-2019
  • (2015)Efficient Conversion of RNA Pseudoknots to Knot-Free Structures Using a Graphical ModelIEEE Transactions on Biomedical Engineering10.1109/TBME.2014.237536062:5(1265-1271)Online publication date: May-2015
  • (2010)Counting hexagonal patches and independent sets in circle graphsProceedings of the 9th Latin American conference on Theoretical Informatics10.1007/978-3-642-12200-2_52(603-614)Online publication date: 19-Apr-2010

Index Terms

  1. Efficiently implementing maximum independent set algorithms on circle graphs

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Journal of Experimental Algorithmics
    ACM Journal of Experimental Algorithmics  Volume 13, Issue
    2009
    482 pages
    ISSN:1084-6654
    EISSN:1084-6654
    DOI:10.1145/1412228
    Issue’s Table of Contents
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 23 February 2009
    Published in JEA Volume 13

    Author Tags

    1. Circle graph
    2. maximum independent set
    3. maximum stable set

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)3
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 11 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)An output sensitive algorithm for computing a maximum independent set of a circle graphInformation Processing Letters10.1016/j.ipl.2010.05.016110:16(630-634)Online publication date: 6-Jan-2019
    • (2015)Efficient Conversion of RNA Pseudoknots to Knot-Free Structures Using a Graphical ModelIEEE Transactions on Biomedical Engineering10.1109/TBME.2014.237536062:5(1265-1271)Online publication date: May-2015
    • (2010)Counting hexagonal patches and independent sets in circle graphsProceedings of the 9th Latin American conference on Theoretical Informatics10.1007/978-3-642-12200-2_52(603-614)Online publication date: 19-Apr-2010

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media