@article{Marx, author = {D. Marx}, title = {A short proof of the {NP}-completeness of minimum sum interval coloring}, journal = {Operations Research Letters}, volume = 33, number = 4, pages = {382--384}, year = 2005 } @article{McConnell, author = {Ross M. McConnell}, title = {Linear-Time Recognition of Circular-Arc Graphs}, journal = {Algorithmica}, volume = {37}, number = {2}, year = {2003}, pages = {93-147}, ee = {http://dx.doi.org/10.1007/s00453-003-1032-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{gz, author = {D.J. Guan and X. Zhu}, title = {A coloring problem for weighted graphs}, journal = {Information Processing Letters}, volume = 61, pages = {77--81}, year = 1997, } @article{ChrobakSlusarek, author = {M. Chrobak and M. \'{S}lusarek}, title = {On some packing problems related to dynamic storage allocation}, journal = {Informatique th\'{e}orique et Applications/Theoretical Informatics and Applications}, volume = 22, number = 4, pages = {487--499}, year = 1988 } @inproceedings{Guruswami, author = "V. Guruswami", title = "Inapproximability results for set splitting and satisfiability problems with no mixed clauses", booktitle = "{APPROX}", pages = "155--166", year = 2000 } @article{LovaszSaksTrotter, author = {L. Lov\'{a}sz and M. Saks and W.T. Trotter}, title = {An on-line graph coloring algorithm with sublinear performance ratio}, journal = {Discrete Math.}, volume = 75, pages = {319--325}, year = 1989 } @article{Irani, author = {S. Irani}, title = {Coloring Inductive Graphs On-Line}, journal = {Algorithmica}, volume = 11, number = 1, pages = {53--72}, year = 1994 } @article{KiersteadTrotter, author = {H.A. Kierstead and W.T. Trotter}, title = {An extremal problem in recursive combinatorics}, journal = {Congressus Numerantium}, volume = 33, pages = {143--153}, year = 1981 } @inproceedings{CorneilOlariuStewart, author = {D.G. Corneil and S. Olariu and L. Stewart}, title = {The Ultimate Interval Graph Recognition Algorithm? (Extended Abstract)}, booktitle = {Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms}, year = 1998, pages = {175--180} } @inproceedings{GovindarajanRengarajan, author = {R. Govindarajan and S. Rengarajan}, title = {Buffer Allocation in Regular Dataflow Networks: An Approach Based on Coloring Circular-Arc Graphs}, booktitle = {Proceedings of the 2nd International Conference on High Performance Computing}, year = 1996 } @article{BakerCoffman, author = {B.S. Baker and E.G. Coffman}, title = {Mutual Exclusion Scheduling}, journal = {Theoretical Computer Science}, volume = 162, year = 1996, pages = {225--243} } @article{BarNoyHalldorssonShachnaiTamir, author = {A. Bar-Noy and M. Bellare and M. Halldorsson and H. Shachnai and T. Tamir}, title = {On Chromatic sums and distributed resource allocation}, journal = {Information and Computation}, volume = 140, year = 1998, pages = {183--202} } @unpublished{Briggs, author = {P. Briggs}, title = {Register Allocation via graph coloring}, note = {Ph.D. Thesis, Rice University}, year = 1992 } @article{Chaitin, author = {G.J. Chaitin}, title = {Register Allocation and spilling via coloring}, journal = {ACM SIGPLAN Notices}, volume = 17, number = 6, pages = {98--105}, year = 1982 } @article{Ershov, author = {A.P. Ershov}, title = {Alpha - an automatic programming system of high efficiency}, journal = {Journal of the ACM}, volume = 13, number = 1, year = 1966 } @article{Fabri, author = {J. Fabri}, title = {Automatic Storage optimization}, journal = {ACM SIGPLAN Notices: Proceedings of the ACM SIGPLAN '79 on Compiler Construction}, volume = 14, number = 8, pages = {83--91}, year = 1979 } @inproceedings{Gergov99, author = {J. Gergov}, title = {Algorithms for Compile-Time Memory Optimization}, booktitle = {Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms}, year = 1999, pages = "S907--S908" } @book{Golumbic, author = {M.C. Golumbic}, title = {Algorithmic graph theory and perfect graphs}, publisher = {Academic Press, NY}, year = 1980 } @article{Hastad, author = {J. H{\aa}stad}, title = {Some optimal inapproximability results}, journal = {Journal of the ACM}, volume = 48, pages = {798--859}, year = 2001 } @article{Szkaliczki, author = {T. Szkaliczki}, title = {Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is {NP}-Complete}, journal = {SIAM Journal of Computing}, volume = 29, number= 1, year = 1999 } @book{GareyJohnson, author = {M.R. Garey and D.S. Johnson}, title = {Computers and Intractability: A Guide to the theory of {NP}-completeness}, publisher = {W.H. Freeman and Company, San Fransisco}, year = 1979 } @article{Kierstead88, author = {H.A. Kierstead}, title = {The Linearity of First-Fit Coloring of Interval Graphs}, journal = {SIAM J. Discrete Math}, volume = 1, pages = {526--530}, year = 1988 } @article{Kierstead91, author = {H.A. Kierstead}, title = {A Polynomial Time Approximation Algorithm for Dynamic Storage Allocation}, journal = {Discrete Mathematics}, volume = 88, pages = {231--237}, year = 1991 } @article{KiersteadQin, author = {H.A. Kierstead and J. Qin}, title = {Coloring Interval Graphs with First-Fit}, journal = {Discrete Mathematics}, volume = 144, pages = {47--57}, year = 1995 } @inproceedings{Gergov96, author = {J. Gergov}, title = {Approximation Algorithms for Dynamic Storage Allocation}, booktitle = {Proceedings of the 4th European Symposium on Algorithms: Lecture Notes in Computer Science 1136}, year = 1996, pages = {52--61} } @article{BuchsbaumKarloffKenyonReingoldThorup, author = {Adam L. Buchsbaum and Howard Karloff and Claire Kenyon and Nick Reingold and Mikkel Thorup}, title = {{OPT} Versus {LOAD} in Dynamic Storage Allocation}, journal = {SIAM J. Comput.}, volume = {33}, number = {3}, year = {2004}, issn = {0097-5397}, pages = {632--646}, doi = {http://dx.doi.org/10.1137/S0097539703423941}, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, } @inproceedings{PemmarajuRamanVaradarajan, author = {S.V. Pemmaraju and R. Raman and K. Varadarajan}, title = {Buffer minimization using max-coloring}, booktitle = {Proceedings of The ACM-SIAM Symposium on Discrete Algorithms (SODA)}, year = 2004, pages = {562--571} } @unpublished{BrightwellKiersteadTrotter, author = {G. Brightwell and H. A. Kierstead and W. T. Trotter}, title = {A note on the first-fit coloring of interval graphs}, note = {personal communication}, year = 2003 } @inproceedings{AdamyErlebach, author = "U. Adamy and T. Erlebach", editor = {Klaus Jansen and Roberto Solis-Oba}, title = "Online Coloring of Intervals with Bandwidth", booktitle = "First International Workshop on Approximation and Online Algorithms, (WAOA 2003)", pages = "1--12", publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {2909}, year = {2004} } @inproceedings{Narayanaswamy, author = {N.S. Narayanaswamy}, title = {Dynamic Storage Allocation and On-line Coloring Interval Graphs}, booktitle = {Tenth International Computing and Combinatorics Conference, (COCOON)}, year = 2004, } @unpublished{NarayanaswamyBabu, author = {N.S. Narayanaswamy and R. Subhash Babu}, title = {Analysis of First-fit coloring of interval graphs}, note = {personal communication}, year = 2004, } @article{GareyJohnsonMillerPapadimitriou, author = {M.R. Garey and D.S. Johnson and G.L. Miller and C. H. Papadimitriou}, title = {The complexity of coloring circular-arcs and chords}, journal = {SIAM Journal of Algebraic Discrete Methods}, volume = 1, number = 2, pages = {216--227}, year = 1980 } @inproceedings{Sethi, author = {Ravi Sethi}, title = {Complete register allocation problems}, booktitle = {STOC '73: Proceedings of the fifth annual ACM symposium on Theory of computing}, year = {1973}, pages = {182--195}, location = {Austin, Texas, United States}, doi = {http://doi.acm.org/10.1145/800125.804049}, publisher = {ACM}, address = {New York, NY, USA}, } @inproceedings{LeePalsbergPereira, author = {J.K. Lee and J. Palsberg and F.M.Q. Pereira}, title = {Aliased Register Allocation for Straight-Line Programs Is {NP}-Complete}, booktitle={Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP): Springer Lecture Notes in Computer Science: 4596/2007}, pages={680--691}, year = 2007 } @inproceedings{GuoGarzaranPadua, author = {J. Guo and M.J. Garzar\'{a}n and D. Padua}, title="The Power of {B}elady's Algorithm in Register Allocation for Long Basic Blocks", booktitle={LCPC 2003: Proceedings of the 16th International Workshop on Languages and Compilers for Parallel Computing: Springer Lecture Notes in Computer Science: 2958/2004}, pages = {374--390}, year = 2004 } @inproceedings{GoodmanHsu, author = {J. R. Goodman and W.-C. Hsu}, title = {Code scheduling and register allocation in large basic blocks}, booktitle = {ICS '88: Proceedings of the 2nd International conference on Supercomputing}, year = {1988}, isbn = {0-89791-272-1}, pages = {442--452}, location = {St. Malo, France}, doi = {http://doi.acm.org/10.1145/55364.55407}, publisher = {ACM}, address = {New York, NY, USA}, } @article{PolettoSarkar, author = {Massimiliano Poletto and Vivek Sarkar}, title = {Linear scan register allocation}, journal = {ACM Trans. Program. Lang. Syst.}, volume = {21}, number = {5}, year = {1999}, issn = {0164-0925}, pages = {895--913}, doi = {http://doi.acm.org/10.1145/330249.330250}, publisher = {ACM}, address = {New York, NY, USA}, } @article{AzarFiatLevyNarayanaswamy, author = {Yossi Azar and Amos Fiat and Meital Levy and N. S. Narayanaswamy}, title = {An improved algorithm for online coloring of intervals with bandwidth}, journal = {Theor. Comput. Sci.}, volume = {363}, number = {1}, year = {2006}, pages = {18-27}, ee = {http://dx.doi.org/10.1016/j.tcs.2006.06.014}, bibsource = {DBLP, http://dblp.uni-trier.de} }