@incollection{Mehlhorn/09,
AUTHOR = {Mehlhorn, Kurt},
TITLE = {Assigning papers to referees},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {1-2},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/f485lm762l364626/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Papadimitriou/09,
AUTHOR = {Papadimitriou, Christos H.},
TITLE = {Algorithmic game theory: A snapshot},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {3-11},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/0384rux4401643j4/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Agnarsson-Halldorsson-Losievskaja/09,
AUTHOR = {Agnarsson, Geir and Halld{\'o}rsson, Magn{\'u}s M. and Losievskaja, Elena},
TITLE = {SDP-based algorithms for maximum independent set problems on hypergraphs},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {12-23},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/w131375587654347/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ailon-Liberty/09,
AUTHOR = {Ailon, Nir and Liberty, Edo},
TITLE = {Correlation Clustering revisited: The ``true'' cost of error minimization problems},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {24-36},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/k6q585r57g17vt40/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ajtai-Feldman-Hassidim-Nelson/09,
AUTHOR = {Ajtai, Mikl{\'o}s and Feldman, Vitaly and Hassidim, Avinatan and Nelson, Jelani},
TITLE = {Sorting and selection with imprecise comparisons},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {37-48},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/h67247079296u147/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Alon-Lokshtanov-Saurabh/09,
AUTHOR = {Alon, Noga and Lokshtanov, Daniel and Saurabh, Saket},
TITLE = {Fast FAST},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {49-58},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/k45p655773056g77/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Amano/09,
AUTHOR = {Amano, Kazuyuki},
TITLE = {Bounds on the size of small depth circuits for approximating majority},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {59-70},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/u584j227175471nw/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Amini-Fomin-Saurabh/09,
AUTHOR = {Amini, Omid and Fomin, Fedor V. and Saurabh, Saket},
TITLE = {Counting subgraphs via homomorphisms},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {71-82},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/cg2w8p5v28410435/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Andoni-Indyk-Onak-Rubinfeld/09,
AUTHOR = {Andoni, Alexandr and Indyk, Piotr and Onak, Krzysztof and Rubinfeld, Ronitt},
TITLE = {External sampling},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {83-94},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/rm28576538318011/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Arackaparambil-Brody-Chakrabarti/09,
AUTHOR = {Arackaparambil, Chrisil and Brody, Joshua and Chakrabarti, Amit},
TITLE = {Functional monitoring without monotonicity},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {95-106},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/v87524876mt32668/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Arbitman-Naor-Segev/09,
AUTHOR = {Arbitman, Yuriy and Naor, Moni and Segev, Gil},
TITLE = {De-amortized cuckoo hashing: Provable worst-case performance and experimental results},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {107-118},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/d5187mm887547j31/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Arora-Steurer-Wigderson/09,
AUTHOR = {Arora, Sanjeev and Steurer, David and Wigderson, Avi},
TITLE = {Towards a study of low-complexity graphs},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {119-131},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/e535v2230k36152l/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Aubrun-Beal/09,
AUTHOR = {Aubrun, Nathalie and B{\'e}al, Marie-Pierre},
TITLE = {Decidability of conjugacy of tree-shifts of finite type},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {132-143},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/k2568m1662kp06j5/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bansal-Chan-Pruhs-Katz/09,
AUTHOR = {Bansal, Nikhil and Chan, Ho-Leung and Pruhs, Kirk and Katz, Dmitriy},
TITLE = {Improved bounds for speed scaling in devices obeying the cube-root rule},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {144-155},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/l010123h0m830727/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Becchetti-Koutsoupias/09,
AUTHOR = {Becchetti, Luca and Koutsoupias, Elias},
TITLE = {Competitive analysis of aggregate max in windowed streaming},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {156-170},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/u575vk1222035521/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bille-Thorup/09,
AUTHOR = {Bille, Philip and Thorup, Mikkel},
TITLE = {Faster regular expression matching},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {171-182},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/4h74712x76536863/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Boros-Makino/09,
AUTHOR = {Boros, Endre and Makino, Kazuhisa},
TITLE = {A fast and simple parallel algorithm for the monotone duality problem},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {183-194},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/52l588275mk008u0/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Buhrman-Fortnow-Santhanam/09,
AUTHOR = {Buhrman, Harry and Fortnow, Lance and Santhanam, Rahul},
TITLE = {Unconditional lower bounds against advice},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {195-209},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/v7740pn3q174p0u2/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chakaravarthy-Pandit-Roy-Sabharwal/09,
AUTHOR = {Chakaravarthy, Venkatesan T. and Pandit, Vinayaka and Roy, Sambuddha and Sabharwal, Yogish},
TITLE = {Approximating decision trees with multiway branches},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {210-221},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/e651212l57j26504/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chakrabarti-Cormode-McGregor/09,
AUTHOR = {Chakrabarti, Amit and Cormode, Graham and McGregor, Andrew},
TITLE = {Annotations in data streams},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {222-234},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/wm4025p687274370/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chandran-Gopalkrishnan-Reif/09,
AUTHOR = {Chandran, Harish and Gopalkrishnan, Nikhil and Reif, John},
TITLE = {The tile complexity of linear assemblies},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {235-253},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/n1436613156341q1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chekuri-Korula/09,
AUTHOR = {Chekuri, Chandra and Korula, Nitish},
TITLE = {A graph reduction step preserving element-connectivity and applications},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {254-265},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/v86261412871m277/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Immorlica-Karlin-Mahdian-Rudra/09,
AUTHOR = {Chen, Ning and Immorlica, Nicole and Karlin, Anna R. and Mahdian, Mohammad and Rudra, Atri},
TITLE = {Approximating matches made in heaven},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {266-278},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/vm554vj780253g67/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chien-Sinclair/09,
AUTHOR = {Chien, Steve and Sinclair, Alistair},
TITLE = {Strong and Pareto price of anarchy in congestion games},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {279-291},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/p37t058875522347/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Coja-Oghlan/09,
AUTHOR = {Coja-Oghlan, Amin},
TITLE = {A better algorithm for random $k$-SAT},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {292-303},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/8q4m8482w742v851/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cygan-Pilipczuk/09,
AUTHOR = {Cygan, Marek and Pilipczuk, Marcin},
TITLE = {Exact and approximate bandwidth},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {304-315},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/981402h1h2838258/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Demaine-Hajiaghayi-Kawarabayashi/09a,
AUTHOR = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Kawarabayashi, Ken-ichi},
TITLE = {Approximation algorithms via structural results for apex-minor-free graphs},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {316-327},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/q32p41g322042808/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Demaine-Hajiaghayi-Klein/09,
AUTHOR = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Klein, Philip N.},
TITLE = {Node-weighted Steiner tree and group Steiner tree in planar graphs},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {328-340},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/983762l2481h024p/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Demaine-Landau-Weimann/09,
AUTHOR = {Demaine, Erik D. and Landau, Gad M. and Weimann, Oren},
TITLE = {On Cartesian trees and range minimum queries},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {341-353},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/1u44tj7102525012/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dietzfelbinger-Rink/09,
AUTHOR = {Dietzfelbinger, Martin and Rink, Michael},
TITLE = {Applications of a splitting trick},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {354-365},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/27w12p275w8njju3/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Doerr-Friedrich-Sauerwald/09,
AUTHOR = {Doerr, Benjamin and Friedrich, Tobias and Sauerwald, Thomas},
TITLE = {Quasirandom rumor spreading: Expanders, push vs. pull, and robustness},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {366-377},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/ghw78vt773q31608/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dom-Lokshtanov-Saurabh/09,
AUTHOR = {Dom, Michael and Lokshtanov, Daniel and Saurabh, Saket},
TITLE = {Incompressibility through colors and IDs},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {378-389},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/t067240107835672/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Draisma-Kushilevitz-Weinreb/09,
AUTHOR = {Draisma, Jan and Kushilevitz, Eyal and Weinreb, Enav},
TITLE = {Partition arguments in multiparty communication complexity},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {390-402},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/j53086n600q0286w/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Durand-Romashchenko-Shen/09,
AUTHOR = {Durand, Bruno and Romashchenko, Andrei and Shen, Alexander},
TITLE = {High complexity tilings with sparse errors},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {403-414},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/6272v382321694ul/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Elsasser-Sauerwald/09,
AUTHOR = {Els{\"a}sser, Robert and Sauerwald, Thomas},
TITLE = {Tight bounds for the cover time of multiple random walks},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {415-426},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/t3021650100w96p1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Emek-Fraigniaud-Korman-Rosen/09,
AUTHOR = {Emek, Yuval and Fraigniaud, Pierre and Korman, Amos and Ros{\'e}n, Adi},
TITLE = {Online computation with advice},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {427-438},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/b8v2g85v25067k83/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Farzan-Munro/09,
AUTHOR = {Farzan, Arash and Munro, J. Ian},
TITLE = {Dynamic succinct ordered trees},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {439-450},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/x468870507238jh0/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Farzan-Raman-Rao/09,
AUTHOR = {Farzan, Arash and Raman, Rajeev and Rao, S. Srinivasa},
TITLE = {Universal succinct representations of trees?},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {451-462},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/q5764m33n48x4q66/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fellows-Fomin-Lokshtanov-Losievskaja-Rosamond-Saurabh/09,
AUTHOR = {Fellows, Michael R. and Fomin, Fedor V. and Lokshtanov, Daniel and Losievskaja, Elena and Rosamond, Frances A. and Saurabh, Saket},
TITLE = {Distortion is fixed parameter tractable},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {463-474},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/72r170r238610153/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gfeller-Sanders/09,
AUTHOR = {Gfeller, Beat and Sanders, Peter},
TITLE = {Towards optimal range medians},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {475-486},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/d065688448834048/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Golovin/09,
AUTHOR = {Golovin, Daniel},
TITLE = {B-treaps: A uniquely represented alternative to B-trees},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {487-499},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/xw34042667865g6t/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gopalan-ODonnell-Servedio-Shpilka-Wimmer/09,
AUTHOR = {Gopalan, Parikshit and O'Donnell, Ryan and Servedio, Rocco A. and Shpilka, Amir and Wimmer, Karl},
TITLE = {Testing Fourier dimensionality and sparsity},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {500-512},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/p70071h89383j760/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Guha-Huang/09,
AUTHOR = {Guha, Sudipto and Huang, Zhiyi},
TITLE = {Revisiting the direct sum theorem and space lower bounds in random order streams},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {513-524},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/y0557lr33182uvm2/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Halldorsson-Wattenhofer/09,
AUTHOR = {Halld{\'o}rsson, Magn{\'u}s M. and Wattenhofer, Roger},
TITLE = {Wireless communication is in APX},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {525-536},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/8q323x217502q454/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Holub-Nowotka/09,
AUTHOR = {Holub, {\v{S}}t{\v{e}}p{\'a}n and Nowotka, Dirk},
TITLE = {The Ehrenfeucht-Silberger problem},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {537-548},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/q617059103361t84/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hoyrup-Rojas/09a,
AUTHOR = {Hoyrup, Mathieu and Rojas, Crist{\'o}bal},
TITLE = {Applications of effective probability theory to Martin-L{\"o}f randomness},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {549-561},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/16201126166vpk35/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jansen/09,
AUTHOR = {Jansen, Klaus},
TITLE = {An EPTAS for scheduling jobs on uniform processors: Using an MILP relaxation with a constant number of integral variables},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {562-573},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/222387h914004888/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kavitha-Mestre-Nasre/09,
AUTHOR = {Kavitha, Telikepalli and Mestre, Juli{\'a}n and Nasre, Meghana},
TITLE = {Popular mixed matchings},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {574-584},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/a375w2t71721172l/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kayal-Nezhmetdinov/09,
AUTHOR = {Kayal, Neeraj and Nezhmetdinov, Timur},
TITLE = {Factoring groups efficiently},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {585-596},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/t8g2u774n186r64u/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Khuller-Saha/09,
AUTHOR = {Khuller, Samir and Saha, Barna},
TITLE = {On finding dense subgraphs},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {597-608},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/c0q858675m627684/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Klivans-Long-Servedio/09,
AUTHOR = {Klivans, Adam R. and Long, Philip M. and Servedio, Rocco A.},
TITLE = {Learning halfspaces with malicious noise},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {609-621},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/v31136u7n126t384/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kobayashi-Le_Gall-Nishimura-Rotteler/09,
AUTHOR = {Kobayashi, Hirotada and Le Gall, Fran{\c{c}}ois and Nishimura, Harumichi and R{\"o}tteler, Martin},
TITLE = {General scheme for perfect quantum network coding with free classical communication},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {622-633},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/d582132730028521/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Koufogiannakis-Young/09,
AUTHOR = {Koufogiannakis, Christos and Young, Neal E.},
TITLE = {Greedy $\Delta$-approximation algorithm for covering with arbitrary constraints and submodular cost},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {634-652},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/m622330h8x80751q/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Koutis-Williams/09,
AUTHOR = {Koutis, Ioannis and Williams, Ryan},
TITLE = {Limits and applications of group algebras for parameterized problems},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {653-664},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/w3174vl187074444/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lam-Lee-Ting-To-Wong/09,
AUTHOR = {Lam, Tak-Wah and Lee, Lap-Kei and Ting, Hing-Fung and To, Isaac K.K. and Wong, Prudence W.H.},
TITLE = {Sleep with guilt and work faster to minimize flow plus energy},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {665-676},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/x6tj467r8v431775/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Mastrolilli-Svensson/09,
AUTHOR = {Mastrolilli, Monaldo and Svensson, Ola},
TITLE = {Improved bounds for flow shop scheduling},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {677-688},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/y143k45155h5647l/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{McDermid/09,
AUTHOR = {McDermid, Eric},
TITLE = {A 3/2-approximation algorithm for general stable marriage},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {689-700},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/p3332l36788t8861/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Morizumi/09,
AUTHOR = {Morizumi, Hiroki},
TITLE = {Limiting negations in formulas},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {701-712},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/g4582v3g54142382/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Nederlof/09,
AUTHOR = {Nederlof, Jesper},
TITLE = {Fast polynomial-space algorithms using M{\"o}bius inversion: Improving on Steiner tree and related problems},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {713-725},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/qh3057h235032j15/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Nies/09,
AUTHOR = {Nies, Andr{\'e}},
TITLE = {Superhighness and strong jump traceability},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {726-737},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/r3g54r320255k786/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Roland-Szegedy/09,
AUTHOR = {Roland, J{\'e}r{\'e}mie and Szegedy, Mario},
TITLE = {Amortized communication complexity of distributions},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {738-749},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/21pu0rl2p414x822/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Vallee-Clement-Fill-Flajolet/09,
AUTHOR = {Vall{\'e}e, Brigitte and Cl{\'e}ment, Julien and Fill, James Allen and Flajolet, Philippe},
TITLE = {The number of symbol comparisons in QuickSort and QuickSelect},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {750-763},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/37w5j8032883764u/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Weimann-Yuster/09,
AUTHOR = {Weimann, Oren and Yuster, Raphael},
TITLE = {Computing the girth of a planar graph in $O(n \log n)$ time},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {764-773},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/b54r88274482q404/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ye-Borodin/09,
AUTHOR = {Ye, Yuli and Borodin, Allan},
TITLE = {Elimination graphs},
BOOKTITLE = {Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP'2009, Part I (Rhodes, Greece, July 5-12, 2009)},
SERIES = {LNCS},
VOLUME = {5555},
PAGES = {774-785},
YEAR = {2009},
EDITOR = {Albers, Susanne and Marchetti-Spaccamela, Alberto and Matias, Yossi and Nikoletseas, Sotiris and Thomas, Wolfgang},
URL = {http://springerlink.metapress.com/content/k24328581w801524/fulltext.pdf" title="Download PDF (205.3 KB)"><span>Download PDF (205.3 KB)</span></a></li> 	</ul></li><li class="primitive primitiveResource Backmatter"><p class="title">Back matter</p><ul class="resources fulltextResources" data-ftxUrl="/content/978-3-642-02926-4/#section=177896"> 		<li><a class="sprite pdf-resource-spritehttp://springerlink.metapress.com/content/978-3-642-02926-4/back-matter.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}