Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, Wolfgang Thomas
Proceedings of the 36th International Colloquium on Automata, Languages and Programming, Part I
ICALP (1), 2009.

@proceedings{ICALP-v1-2009,
	address       = "Rhodes, Greece",
	doi           = "10.1007/978-3-642-02927-1",
	editor        = "Susanne Albers and Alberto Marchetti-Spaccamela and Yossi Matias and Sotiris E. Nikoletseas and Wolfgang Thomas",
	isbn          = "978-3-642-02926-4",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 36th International Colloquium on Automata, Languages and Programming, Part I}",
	volume        = 5555,
	year          = 2009,
}

Contents (64 items)

8 ×#algorithm
7 ×#approximate
6 ×#bound
6 ×#graph
6 ×#performance
6 ×#problem
4 ×#communication
4 ×#complexity
3 ×#multi
3 ×#random

ICALP-v1-2009-Mehlhorn

Assigning Papers to Referees (KM), pp. 1–2.

ICALP-v1-2009-Papadimitriou #algorithm #game studies

Algorithmic Game Theory: A Snapshot (CHP), pp. 3–11.

ICALP-v1-2009-AgnarssonHL #algorithm #independence #problem #set

SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs (GA, MMH, EL), pp. 12–23.

ICALP-v1-2009-AilonL #clustering #correlation #cost analysis #fault #problem

Correlation Clustering Revisited: The “True” Cost of Error Minimization Problems (NA, EL), pp. 24–36.

ICALP-v1-2009-AjtaiFHN #sorting

Sorting and Selection with Imprecise Comparisons (MA, VF, AH, JN), pp. 37–48.

ICALP-v1-2009-AlonLS #performance

Fast FAST (NA, DL, SS), pp. 49–58.

ICALP-v1-2009-Amano #approximate #bound

Bounds on the Size of Small Depth Circuits for Approximating Majority (KA), pp. 59–70.

ICALP-v1-2009-AminiFS #morphism

Counting Subgraphs via Homomorphisms (OA, FVF, SS), pp. 71–82.

ICALP-v1-2009-AndoniIOR

External Sampling (AA, PI, KO, RR), pp. 83–94.

ICALP-v1-2009-ArackaparambilBC #functional #monitoring

Functional Monitoring without Monotonicity (CA, JB, AC), pp. 95–106.

ICALP-v1-2009-ArbitmanNS #performance #worst-case

De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results (YA, MN, GS), pp. 107–118.

ICALP-v1-2009-AroraSW #case study #graph #towards

Towards a Study of Low-Complexity Graphs (SA, DS, AW), pp. 119–131.

ICALP-v1-2009-AubrunB #decidability #finite

Decidability of Conjugacy of Tree-Shifts of Finite Type (NA, MPB), pp. 132–143.

ICALP-v1-2009-BansalCPK #bound #scalability

Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule (NB, HLC, KP, DK), pp. 144–155.

ICALP-v1-2009-BecchettiK #analysis #streaming

Competitive Analysis of Aggregate Max in Windowed Streaming (LB, EK), pp. 156–170.

ICALP-v1-2009-BilleT #performance #regular expression

Faster Regular Expression Matching (PB, MT), pp. 171–182.

ICALP-v1-2009-BorosM #algorithm #parallel #performance #problem

A Fast and Simple Parallel Algorithm for the Monotone Duality Problem (EB, KM), pp. 183–194.

ICALP-v1-2009-BuhrmanFS #bound

Unconditional Lower Bounds against Advice (HB, LF, RS), pp. 195–209.

ICALP-v1-2009-ChakaravarthyPRS #approximate #branch #multi

Approximating Decision Trees with Multiway Branches (VTC, VP, SR, YS), pp. 210–221.

ICALP-v1-2009-ChakrabartiCM #data type

Annotations in Data Streams (AC, GC, AM), pp. 222–234.

ICALP-v1-2009-ChandranGR #complexity #linear

The Tile Complexity of Linear Assemblies (HC, NG, JHR), pp. 235–253.

ICALP-v1-2009-ChekuriK #graph #reduction

A Graph Reduction Step Preserving Element-Connectivity and Applications (CC, NK), pp. 254–265.

ICALP-v1-2009-ChenIKMR #approximate

Approximating Matches Made in Heaven (NC, NI, ARK, MM, AR), pp. 266–278.

ICALP-v1-2009-ChienS #game studies

Strong and Pareto Price of Anarchy in Congestion Games (SC, AS), pp. 279–291.

ICALP-v1-2009-Coja-Oghlan #algorithm #random #satisfiability

A Better Algorithm for Random k-SAT (ACO), pp. 292–303.

ICALP-v1-2009-CyganP #approximate

Exact and Approximate Bandwidth (MC, MP), pp. 304–315.

ICALP-v1-2009-DemaineHK #algorithm #approximate #graph

Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs (EDD, MH, KiK), pp. 316–327.

ICALP-v1-2009-DemaineHK09a #graph

Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs (EDD, MH, PNK), pp. 328–340.

ICALP-v1-2009-DemaineLW #on the #query

On Cartesian Trees and Range Minimum Queries (EDD, GML, OW), pp. 341–353.

ICALP-v1-2009-DietzfelbingerR

Applications of a Splitting Trick (MD, MR), pp. 354–365.

ICALP-v1-2009-DoerrFS #robust

Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness (BD, TF, TS), pp. 366–377.

ICALP-v1-2009-DomLS

Incompressibility through Colors and IDs (MD, DL, SS), pp. 378–389.

ICALP-v1-2009-DraismaKW #communication #complexity #multi

Partition Arguments in Multiparty Communication Complexity (JD, EK, EW), pp. 390–402.

ICALP-v1-2009-DurandRS #complexity #fault

High Complexity Tilings with Sparse Errors (BD, AER, AS), pp. 403–414.

ICALP-v1-2009-ElsasserS #bound #multi #random

Tight Bounds for the Cover Time of Multiple Random Walks (RE, TS), pp. 415–426.

ICALP-v1-2009-EmekFKR #online

Online Computation with Advice (YE, PF, AK, AR), pp. 427–438.

ICALP-v1-2009-FarzanM #order

Dynamic Succinct Ordered Trees (AF, JIM), pp. 439–450.

ICALP-v1-2009-FarzanRR #question

Universal Succinct Representations of Trees? (AF, RR, SSR), pp. 451–462.

ICALP-v1-2009-FellowsFLLRS #parametricity

Distortion Is Fixed Parameter Tractable (MRF, FVF, DL, EL, FAR, SS), pp. 463–474.

ICALP-v1-2009-GfellerS #towards

Towards Optimal Range Medians (BG, PS), pp. 475–486.

ICALP-v1-2009-Golovin #named

B-Treaps: A Uniquely Represented Alternative to B-Trees (DG), pp. 487–499.

ICALP-v1-2009-GopalanOSSW #fourier #testing

Testing Fourier Dimensionality and Sparsity (PG, RO, RAS, AS, KW), pp. 500–512.

ICALP-v1-2009-GuhaH #bound #order #random #theorem

Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams (SG, ZH), pp. 513–524.

ICALP-v1-2009-HalldorssonW #communication

Wireless Communication Is in APX (MMH, RW), pp. 525–536.

ICALP-v1-2009-HolubN #problem

The Ehrenfeucht-Silberger Problem (SH, DN), pp. 537–548.

ICALP-v1-2009-HoyrupR #effectiveness #probability

Applications of Effective Probability Theory to Martin-Löf Randomness (MH, CR), pp. 549–561.

ICALP-v1-2009-Jansen #constant #scheduling #using

An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables (KJ), pp. 562–573.

ICALP-v1-2009-KavithaMN

Popular Mixed Matchings (TK, JM, MN), pp. 574–584.

ICALP-v1-2009-KayalN

Factoring Groups Efficiently (NK, TN), pp. 585–596.

ICALP-v1-2009-KhullerS #on the

On Finding Dense Subgraphs (SK, BS), pp. 597–608.

ICALP-v1-2009-KlivansLS #learning

Learning Halfspaces with Malicious Noise (ARK, PML, RAS), pp. 609–621.

ICALP-v1-2009-KobayashiGNR #communication #network #quantum

General Scheme for Perfect Quantum Network Coding with Free Classical Communication (HK, FLG, HN, MR), pp. 622–633.

ICALP-v1-2009-KoufogiannakisY #algorithm #approximate #constraints

Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost (CK, NEY), pp. 634–652.

ICALP-v1-2009-KoutisW #algebra #problem

Limits and Applications of Group Algebras for Parameterized Problems (IK, RW), pp. 653–664.

ICALP-v1-2009-LamLTTW #energy #performance

Sleep with Guilt and Work Faster to Minimize Flow Plus Energy (TWL, LKL, HFT, IKKT, PWHW), pp. 665–676.

ICALP-v1-2009-MastrolilliS #bound #scheduling

Improved Bounds for Flow Shop Scheduling (MM, OS), pp. 677–688.

ICALP-v1-2009-McDermid #algorithm #approximate

A 3/2-Approximation Algorithm for General Stable Marriage (EM), pp. 689–700.

ICALP-v1-2009-Morizumi

Limiting Negations in Formulas (HM), pp. 701–712.

ICALP-v1-2009-Nederlof #algorithm #performance #problem #using

Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems (JN), pp. 713–725.

ICALP-v1-2009-Nies #traceability

Superhighness and Strong Jump Traceability (AN), pp. 726–737.

ICALP-v1-2009-RolandS #communication #complexity

Amortized Communication Complexity of Distributions (JR, MS), pp. 738–749.

ICALP-v1-2009-ValleeCFF

The Number of Symbol Comparisons in QuickSort and QuickSelect (BV, JC, JAF, PF), pp. 750–763.

ICALP-v1-2009-WeimannY #graph

Computing the Girth of a Planar Graph in O(n logn) Time (OW, RY), pp. 764–773.

ICALP-v1-2009-YeB #graph

Elimination Graphs (YY, AB), pp. 774–785.