@incollection{Monien-Dumrauf-Tscheuschner/10,
AUTHOR = {Monien, Burkhard and Dumrauf, Dominic and Tscheuschner, Tobias},
TITLE = {Local search: Simple, successful, but sometimes sluggish},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {1-17},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/g331084340558565/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Welzl/10,
AUTHOR = {Welzl, Emo},
TITLE = {When conflicting constraints can be resolved --- The Lov{\'a}sz Local Lemma and satisfiability},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {18-18},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/1n5m3168217421x0/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {abstract},
}
@incollection{Bonichon-Gavoille-Hanusse-Perkovic/10,
AUTHOR = {Bonichon, Nicolas and Gavoille, Cyril and Hanusse, Nicolas and Perkovi{\'c}, Ljubomir},
TITLE = {Plane spanners of maximum degree six},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {19-30},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/qmk4vkr508084k20/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Briet-de_Oliveira_Filho-Vallentin/10,
AUTHOR = {Bri{\"e}t, Jop and de Oliveira Filho, Fernando M{\'a}rio and Vallentin, Frank},
TITLE = {The positive semidefinite Grothendieck problem with rank constraint},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {31-42},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/238546648114m080/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Amir-Eisenberg-Levy-Porat-Shapira/10,
AUTHOR = {Amir, Amihood and Eisenberg, Estrella and Levy, Avivit and Porat, Ely and Shapira, Natalie},
TITLE = {Cycle detection and correction},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {43-54},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/t52243g2518h2077/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kral/10,
AUTHOR = {Kr{\'a}l', Daniel},
TITLE = {Decomposition width of matroids},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {55-66},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/a20gl7414m2014lv/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bateni-Hajiaghayi-Immorlica-Mahini/10,
AUTHOR = {Bateni, MohammadHossein and Hajiaghayi, MohammadTaghi and Immorlica, Nicole and Mahini, Hamid},
TITLE = {The cooperative game theory foundations of network bargaining games},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {67-78},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/k5316q1762421461/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Harks-Klimm/10,
AUTHOR = {Harks, Tobias and Klimm, Max},
TITLE = {On the existence of pure Nash equilibria in weighted congestion games},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {79-89},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/d11502886216570m/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Borodin-Lucier/10,
AUTHOR = {Borodin, Allan and Lucier, Brendan},
TITLE = {On the limitations of greedy mechanism design for truthful combinatorial auctions},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {90-101},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/v532760385l2540t/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Atserias-Maneva/10,
AUTHOR = {Atserias, Albert and Maneva, Elitza},
TITLE = {Mean-payoff games and propositional proofs},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {102-113},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/u800058x01553902/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Anagnostopoulos-Grandoni-Leonardi-Sankowski/10,
AUTHOR = {Anagnostopoulos, Aris and Grandoni, Fabrizio and Leonardi, Stefano and Sankowski, Piotr},
TITLE = {Online network design with outliers},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {114-126},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/l00522425772w444/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Libert-Yung/10,
AUTHOR = {Libert, Beno{\^{i}}t and Yung, Moti},
TITLE = {Efficient completely non-malleable public key encryption},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {127-139},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/n4847266h424005v/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ito/10,
AUTHOR = {Ito, Tsuyoshi},
TITLE = {Polynomial-space approximation of no-signaling provers},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {140-151},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/e222878064026k05/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Applebaum-Ishai-Kushilevitz/10,
AUTHOR = {Applebaum, Benny and Ishai, Yuval and Kushilevitz, Eyal},
TITLE = {From secrecy to soundness: Efficient verification via secure computation},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {152-163},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/621m5g4648823424/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Iacono-Ozkan/10,
AUTHOR = {Iacono, John and {\"O}zkan, {\"O}zg{\"u}r},
TITLE = {Mergeable dictionaries},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {164-175},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/p84nt2133x315044/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fakcharoenphol-Laekhanukit-Nanongkai/10,
AUTHOR = {Fakcharoenphol, Jittat and Laekhanukit, Bundit and Nanongkai, Danupon},
TITLE = {Faster algorithms for semi-matching problems},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {176-187},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/04233165vh21v72h/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Li-Yi-Zhang/10,
AUTHOR = {Li, Jian and Yi, Ke and Zhang, Qin},
TITLE = {Clustering with diversity},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {188-200},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/1755831r88856411/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Duan/10,
AUTHOR = {Duan, Ran},
TITLE = {New data structures for subgraph connectivity},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {201-212},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/q0604312535980j1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dietzfelbinger-Goerdt-Mitzenmacher-Montanari-Pagh-Rink/10,
AUTHOR = {Dietzfelbinger, Martin and Goerdt, Andreas and Mitzenmacher, Michael and Montanari, Andrea and Pagh, Rasmus and Rink, Michael},
TITLE = {Tight thresholds for cuckoo hashing via XORSAT},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {213-225},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/g2121217u1760u5v/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Cole-Ramachandran/10,
AUTHOR = {Cole, Richard and Ramachandran, Vijaya},
TITLE = {Resource oblivious sorting on multicores},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {226-237},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/h23344092147g248/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jimenez-Martinez/10,
AUTHOR = {Jim{\'e}nez, Rosa M. and Mart{\'{i}}nez, Conrado},
TITLE = {Interval sorting},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {238-249},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/t4t124p165g2733k/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bansal-Khot/10,
AUTHOR = {Bansal, Nikhil and Khot, Subhash},
TITLE = {Inapproximability of hypergraph vertex cover and applications to scheduling problems},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {250-261},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/j5hp1w37663v85p3/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gupta-Nagarajan-Ravi/10,
AUTHOR = {Gupta, Anupam and Nagarajan, Viswanath and Ravi, R.},
TITLE = {Thresholded covering algorithms for robust and max-min optimization},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {262-274},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/k12676p72x1x62rl/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cai-Chen-Lu/10,
AUTHOR = {Cai, Jin-Yi and Chen, Xi and Lu, Pinyan},
TITLE = {Graph homomorphisms with complex values: A dichotomy theorem},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {275-286},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/46275700132p5250/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Bansal-Buchbinder-Naor/10,
AUTHOR = {Bansal, Nikhil and Buchbinder, Niv and Naor, Joseph (Seffi)},
TITLE = {Metrical task systems and the $k$-server problem on HSTs},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {287-298},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/lv83522qhq5p5766/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Eisenbrand-Hahnle-Niemeier-Skutella-Verschae-Wiese/10,
AUTHOR = {Eisenbrand, Friedrich and H{\"a}hnle, Nicolai and Niemeier, Martin and Skutella, Martin and Verschae, Jos{\'e} and Wiese, Andreas},
TITLE = {Scheduling periodic tasks in a hard real-time environment},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {299-311},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/d61x037u1ux2564g/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gupta-Krishnaswamy-Pruhs/10,
AUTHOR = {Gupta, Anupam and Krishnaswamy, Ravishankar and Pruhs, Kirk},
TITLE = {Scalably scheduling power-heterogeneous processors},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {312-323},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/5841r304328557m7/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bansal-Krishnaswamy-Nagarajan/10,
AUTHOR = {Bansal, Nikhil and Krishnaswamy, Ravishankar and Nagarajan, Viswanath},
TITLE = {Better scalable algorithms for broadcast scheduling},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {324-335},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/v4341552407v8356/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Epstein-Levin-van_Stee/10,
AUTHOR = {Epstein, Leah and Levin, Asaf and van Stee, Rob},
TITLE = {Max-min online allocations with a reordering buffer},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {336-347},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/x510350m5q267811/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fountoulakis-Panagiotou/10,
AUTHOR = {Fountoulakis, Nikolaos and Panagiotou, Konstantinos},
TITLE = {Orientability of random hypergraphs and the power of multiple choices},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {348-359},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/e8r0t858j82l7141/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Guruswami-Saket/10,
AUTHOR = {Guruswami, Venkatesan and Saket, Rishi},
TITLE = {On the inapproximability of vertex cover on $k$-partite $k$-uniform hypergraphs},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {360-371},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/p536p035k9442663/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Rue-Sau-Thilikos/10,
AUTHOR = {Ru{\'e}, Juanjo and Sau, Ignasi and Thilikos, Dimitrios M.},
TITLE = {Dynamic programming for graphs on surfaces},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {372-383},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/0135661814l13q02/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kobler-Kuhnert-Laubner-Verbitsky/10,
AUTHOR = {K{\"o}bler, Johannes and Kuhnert, Sebastian and Laubner, Bastian and Verbitsky, Oleg},
TITLE = {Interval graphs: Canonical representation in logspace},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {384-395},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/87178xgr21875xg1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Goldberg-Jerrum/10,
AUTHOR = {Goldberg, Leslie Ann and Jerrum, Mark},
TITLE = {Approximating the partition function of the ferromagnetic Potts model},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {396-407},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/qk5l345v56552424/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Shpilka-Volkovich/10,
AUTHOR = {Shpilka, Amir and Volkovich, Ilya},
TITLE = {On the relation between polynomial identity testing and finding variable disjoint factors},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {408-419},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/a7400138537758g3/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Litow/10,
AUTHOR = {Litow, Bruce},
TITLE = {On sums of roots of unity},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {420-425},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/t6150t0113472731/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dell-Husfeldt-Wahlen/10,
AUTHOR = {Dell, Holger and Husfeldt, Thore and Wahl{\'e}n, Martin},
TITLE = {Exponential time complexity of the permanent and the Tutte polynomial},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {426-437},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/k2n274lpv2727488/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Bhattacharya-DasGupta-Mubayi-Turan/10,
AUTHOR = {Bhattacharya, Amitava and DasGupta, Bhaskar and Mubayi, Dhruv and Tur{\'a}n, Gy{\"o}rgy},
TITLE = {On approximate Horn formula minimization},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {438-450},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/41542h1835k67801/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Beimel-Daniel-Kushilevitz-Weinreb/10,
AUTHOR = {Beimel, Amos and Daniel, Sebastian Ben and Kushilevitz, Eyal and Weinreb, Enav},
TITLE = {Choosing, agreeing, and eliminating in communication complexity},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {451-462},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/l875203ru4pq54ur/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Woodruff/10,
AUTHOR = {Woodruff, David P.},
TITLE = {Additive spanners in nearly quadratic time},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {463-474},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/5424882170765631/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lee-Zhang/10,
AUTHOR = {Lee, Troy and Zhang, Shengyu},
TITLE = {Composition theorems in communication complexity},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {475-489},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/dr6j474613876607/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Grandoni-Rothvoss/10,
AUTHOR = {Grandoni, Fabrizio and Rothvo{\ss}, Thomas},
TITLE = {Network design via core detouring for problems without a core},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {490-502},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/n66533194437p182/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ambos-Spies-Bakibayev/10,
AUTHOR = {Ambos-Spies, Klaus and Bakibayev, Timur},
TITLE = {Weak completeness notions for exponential time},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {503-514},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/m4761931520x2k71/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bojanczyk-Parys/10,
AUTHOR = {Boja{\'n}czyk, Miko{\l}aj and Parys, Pawe{\l}},
TITLE = {Efficient evaluation of nondeterministic automata using factorization forests},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {515-526},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/6456274503xj5u80/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jacobs-Cicalese-Laber-Molinaro/10,
AUTHOR = {Jacobs, Tobias and Cicalese, Ferdinando and Laber, Eduardo and Molinaro, Marco},
TITLE = {On the complexity of searching in trees: Average-case minimization},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {527-539},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/p63x36h6j12w1004/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Krovi-Magniez-Ozols-Roland/10,
AUTHOR = {Krovi, Hari and Magniez, Fr{\'e}d{\'e}ric and Ozols, Maris and Roland, J{\'e}r{\'e}mie},
TITLE = {Finding is as easy as detecting for quantum walks},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {540-551},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/y780j43511u76767/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cheraghchi/10,
AUTHOR = {Cheraghchi, Mahdi},
TITLE = {Improved constructions for non-adaptive threshold group testing},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {552-564},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/qt248u57tmr37474/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Rubinfeld-Xie/10,
AUTHOR = {Rubinfeld, Ronitt and Xie, Ning},
TITLE = {Testing non-uniform $k$-wise independent distributions over product spaces},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {565-581},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/g2025760037143w6/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Gamzu-Segev/10a,
AUTHOR = {Gamzu, Iftah and Segev, Danny},
TITLE = {A sublogarithmic approximation for highway and tollbooth pricing},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {582-593},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/156m56658h3163q1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Makarychev-Manokaran-Sviridenko/10,
AUTHOR = {Makarychev, Konstantin and Manokaran, Rajsekar and Sviridenko, Maxim},
TITLE = {Maximum quadratic assignment problem: Reduction from maximum label cover and LP-based approximation algorithm},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {594-604},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/h3300087x7352553/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Greve-Jorgensen-Dalgaard_Larsen-Truelsen/10,
AUTHOR = {Greve, Mark and J{\o}rgensen, Allan Gr{\o}nlund and Dalgaard Larsen, Kasper and Truelsen, Jakob},
TITLE = {Cell probe lower bounds and approximations for range mode},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {605-616},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/9787885t4677u140/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Guruswami-Khot-ODonnell-Popat-Tulsiani-Wu/10,
AUTHOR = {Guruswami, Venkatesan and Khot, Subhash and O'Donnell, Ryan and Popat, Preyas and Tulsiani, Madhur and Wu, Yi},
TITLE = {SDP gaps for 2-to-1 and other Label-Cover variants},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {617-628},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/r751u746735746q2/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Rudra-Uurtamo/10,
AUTHOR = {Rudra, Atri and Uurtamo, Steve},
TITLE = {Data stream algorithms for codeword testing},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {629-640},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/kg5068j76152337q/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Halldorsson-Halldorsson-Losievskaja-Szegedy/10,
AUTHOR = {Halld{\'o}rsson, Bjarni V. and Halld{\'o}rsson, Magn{\'u}s M. and Losievskaja, Elena and Szegedy, Mario},
TITLE = {Streaming algorithms for independent sets},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {641-652},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/u56216827n575125/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kratsch-Wahlstrom/10,
AUTHOR = {Kratsch, Stefan and Wahlstr{\"o}m, Magnus},
TITLE = {Preprocessing of min ones problems: A dichotomy},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {653-665},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/l453714222320w60/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Xia/10,
AUTHOR = {Xia, Mingji},
TITLE = {Holographic reduction: A domain changed application and its partial converse theorems},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {666-677},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/v66371842421176v/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Grossi-Orlandi-Raman/10,
AUTHOR = {Grossi, Roberto and Orlandi, Alessio and Raman, Rajeev},
TITLE = {Optimal trade-offs for succinct string indexes},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {678-689},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/66v0tl8113368876/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gupta-Nagarajan-Ravi/10a,
AUTHOR = {Gupta, Anupam and Nagarajan, Viswanath and Ravi, R.},
TITLE = {Approximation algorithms for optimal decision trees and adaptive TSP problems},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {690-701},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/55844635822333ll/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Yao-Yung-Zhao/10,
AUTHOR = {Yao, Andrew C. and Yung, Moti and Zhao, Yunlei},
TITLE = {Concurrent knowledge extraction in the public-key model},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {702-714},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/w71gh7q5463m5868/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Patrascu-Thorup/10,
AUTHOR = {P{\v{a}}tra{\c{s}}cu, Mihai and Thorup, Mikkel},
TITLE = {On the $k$-independence required by linear probing and minwise independence},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {715-726},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/x806xt22586714l7/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bjorklund-Husfeldt-Kaski-Koivisto/10a,
AUTHOR = {Bj{\"o}rklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko},
TITLE = {Covering and packing in linear space},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {727-737},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/p211rl33414k5p57/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Georgiadis/10,
AUTHOR = {Georgiadis, Loukas},
TITLE = {Testing 2-vertex connectivity and computing pairs of vertex-disjoint $s-t$ paths in digraphs},
BOOKTITLE = {Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP'2010, Part I (Bordeaux, France, July 6-10, 2010)},
SERIES = {LNCS},
VOLUME = {6198},
PAGES = {738-749},
YEAR = {2010},
EDITOR = {Abramsky, Samson and Gavoille, Cyril and Kirchner, Claude and Meyer auf der Heide, Friedhelm and Spirakis, Paul G.},
URL = {http://springerlink.metapress.com/content/0506t5182433020q/fulltext.pdf" title="Download PDF (214.2 KB)"><span>Download PDF (214.2 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-14164-5/#section=727518"> 		<li><a class="sprite pdf-resource-spritehttp://springerlink.metapress.com/content/978-3-642-14164-5/back-matter.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}