default search action
36th ICALP 2009: Rhodes, Greece - Part I
- Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, Wolfgang Thomas:
Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I. Lecture Notes in Computer Science 5555, Springer 2009, ISBN 978-3-642-02926-4
Invited Lectures
- Kurt Mehlhorn:
Assigning Papers to Referees. 1-2 - Christos H. Papadimitriou:
Algorithmic Game Theory: A Snapshot. 3-11
Contributed Papers
- Geir Agnarsson, Magnús M. Halldórsson
, Elena Losievskaja:
SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs. 12-23 - Nir Ailon, Edo Liberty:
Correlation Clustering Revisited: The "True" Cost of Error Minimization Problems. 24-36 - Miklós Ajtai, Vitaly Feldman
Sorting and Selection with Imprecise Comparisons. 37-48 - Noga Alon, Daniel Lokshtanov, Saket Saurabh:
Fast FAST. 49-58 - Kazuyuki Amano:
Bounds on the Size of Small Depth Circuits for Approximating Majority. 59-70 - Omid Amini, Fedor V. Fomin
Counting Subgraphs via Homomorphisms. 71-82 - Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld:
External Sampling. 83-94 - Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti
Functional Monitoring without Monotonicity. 95-106 - Yuriy Arbitman, Moni Naor, Gil Segev:
De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results. 107-118 - Sanjeev Arora, David Steurer, Avi Wigderson:
Towards a Study of Low-Complexity Graphs. 119-131 - Nathalie Aubrun, Marie-Pierre Béal:
Decidability of Conjugacy of Tree-Shifts of Finite Type. 132-143 - Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs, Dmitriy Katz:
Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule. 144-155 - Luca Becchetti
Competitive Analysis of Aggregate Max in Windowed Streaming. 156-170 - Philip Bille, Mikkel Thorup:
Faster Regular Expression Matching. 171-182 - Endre Boros, Kazuhisa Makino:
A Fast and Simple Parallel Algorithm for the Monotone Duality Problem. 183-194 - Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. 195-209 - Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Yogish Sabharwal:
Approximating Decision Trees with Multiway Branches. 210-221 - Amit Chakrabarti
Annotations in Data Streams. 222-234 - Harish Chandran, Nikhil Gopalkrishnan, John H. Reif:
The Tile Complexity of Linear Assemblies. 235-253 - Chandra Chekuri, Nitish Korula:
A Graph Reduction Step Preserving Element-Connectivity and Applications. 254-265 - Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Atri Rudra:
Approximating Matches Made in Heaven. 266-278 - Steve Chien, Alistair Sinclair:
Strong and Pareto Price of Anarchy in Congestion Games. 279-291 - Amin Coja-Oghlan:
A Better Algorithm for Random k-SAT. 292-303 - Marek Cygan
Exact and Approximate Bandwidth. 304-315 - Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi:
Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs. 316-327 - Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein:
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. 328-340 - Erik D. Demaine, Gad M. Landau, Oren Weimann
On Cartesian Trees and Range Minimum Queries. 341-353 - Martin Dietzfelbinger
Applications of a Splitting Trick. 354-365 - Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald:
Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness. 366-377 - Michael Dom, Daniel Lokshtanov, Saket Saurabh:
Incompressibility through Colors and IDs. 378-389 - Jan Draisma, Eyal Kushilevitz, Enav Weinreb:
Partition Arguments in Multiparty Communication Complexity. 390-402 - Bruno Durand, Andrei E. Romashchenko
High Complexity Tilings with Sparse Errors. 403-414 - Robert Elsässer, Thomas Sauerwald:
Tight Bounds for the Cover Time of Multiple Random Walks. 415-426 - Yuval Emek, Pierre Fraigniaud, Amos Korman, Adi Rosén:
Online Computation with Advice. 427-438 - Arash Farzan, J. Ian Munro:
Dynamic Succinct Ordered Trees. 439-450 - Arash Farzan, Rajeev Raman
Universal Succinct Representations of Trees? 451-462 - Michael R. Fellows
Distortion Is Fixed Parameter Tractable. 463-474 - Beat Gfeller, Peter Sanders:
Towards Optimal Range Medians. 475-486 - Daniel Golovin:
B-Treaps: A Uniquely Represented Alternative to B-Trees. 487-499 - Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio
Testing Fourier Dimensionality and Sparsity. 500-512 - Sudipto Guha, Zhiyi Huang
Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams. 513-524 - Magnús M. Halldórsson
Wireless Communication Is in APX. 525-536 - Stepan Holub, Dirk Nowotka:
The Ehrenfeucht-Silberger Problem. 537-548 - Mathieu Hoyrup, Cristobal Rojas
Applications of Effective Probability Theory to Martin-Löf Randomness. 549-561 - Klaus Jansen:
An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables. 562-573 - Telikepalli Kavitha, Julián Mestre, Meghana Nasre
Popular Mixed Matchings. 574-584 - Neeraj Kayal, Timur Nezhmetdinov:
Factoring Groups Efficiently. 585-596 - Samir Khuller, Barna Saha:
On Finding Dense Subgraphs. 597-608 - Adam R. Klivans, Philip M. Long, Rocco A. Servedio:
Learning Halfspaces with Malicious Noise. 609-621 - Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler
General Scheme for Perfect Quantum Network Coding with Free Classical Communication. 622-633 - Christos Koufogiannakis, Neal E. Young
Greedy D{\ensuremath{\Delta}}-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost. 634-652 - Ioannis Koutis, Ryan Williams
Limits and Applications of Group Algebras for Parameterized Problems. 653-664 - Tak Wah Lam
Sleep with Guilt and Work Faster to Minimize Flow Plus Energy. 665-676 - Monaldo Mastrolilli
Improved Bounds for Flow Shop Scheduling. 677-688 - Eric McDermid:
A 3/2-Approximation Algorithm for General Stable Marriage. 689-700 - Hiroki Morizumi:
Limiting Negations in Formulas. 701-712 - Jesper Nederlof:
Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems. 713-725 - André Nies
Superhighness and Strong Jump Traceability. 726-737 - Jérémie Roland
Amortized Communication Complexity of Distributions. 738-749 - Brigitte Vallée, Julien Clément
The Number of Symbol Comparisons in QuickSort and QuickSelect. 750-763 - Oren Weimann
Computing the Girth of a Planar Graph in O(n logn) Time. 764-773 - Yuli Ye, Allan Borodin:
Elimination Graphs. 774-785
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-26 00:35 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: