Front matter
2702-2705
Analysis of Scheduling Algorithms for Proportionate Fairness
Mike Paterson
2
Advances in the Regularity Method
Yoshiharu Kohayakawa
3-4
Fighting Spam: The Science
Cynthia Dwork
2705
The Consequences of Imre Simon’s Work in the Theory of Automata, Languages, and Semigroups
Jean-Eric Pin
6-15
Querying Priced Information in Databases: The Conjunctive Case
Extended Abstract
Sany Laber, Renato Carmo and Yoshiharu Kohayakawa
16-28
Sublinear Methods for Detecting Periodic Trends in Data Streams
Funda Ergun, S. Muthukrishnan and S. Cenk Sahinalp
29-38
An Improved Data Stream Summary: The Count-Min Sketch and Its Applications
Graham Cormode and S. Muthukrishnan
39-48
Rotation and Lighting Invariant Template Matching
Kimmo Fredriksson, Veli Mäkinen and Gonzalo Navarro
49-58
Computation of the Bisection Width for Random d-Regular Graphs
Josep Díaz, Maria J. Serna and Nicholas C. Wormald
2705
Constrained Integer Partitions
Christian Borgs, Jennifer T. Chayes, Stephan Mertens and Boris Pittel
69-79
Embracing the Giant Component
Abraham Flaxman, David Gamarnik and Gregory B. Sorkin
80-89
Sampling Grid Colorings with Fewer Colors
Dimitris Achlioptas, Mike Molloy, Cristopher Moore and Frank Van Bussel
90-99
The Complexity of Finding Top-Toda-Equivalence-Class Members
Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed J. Zaki and Marius Zimand
100-108
List Partitions of Chordal Graphs
Tomás Feder, Pavol Hell, Sulamita Klein, Loana Tito Nogueira and Fábio Protti
109-118
Bidimensional Parameters and Local Treewidth
Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi and Dimitrios M. Thilikos
119-128
Vertex Disjoint Paths on Clique-Width Bounded Graphs
Extended Abstract
Frank Gurski and Egon Wanke
129-140
On Partitioning Interval and Circular-Arc Graphs into Proper Interval Subgraphs with Applications
Frédéric Gardi
141-151
Collective Tree Exploration
Pierre Fraigniaud, Leszek Gasieniec, Dariusz R. Kowalski and Andrzej Pelc
152-161
Off-Centers: A New Type of Steiner Points for Computing Size-Optimal Quality-Guaranteed Delaunay Triangulations
Alper Üngör
2705
Space-Efficient Algorithms for Computing the Convex Hull of a Simple Polygonal Line in Linear Time
Hervé Brönnimann and Timothy M. Chan
172-180
A Geometric Approach to the Bisection Method
Claudio Gutierrez, Flavio Gutierrez and Maria-Cecilia Rivara
181-192
Improved Linear Expected-Time Algorithms for Computing Maxima
H. K. Dai and X. W. Zhang
193-202
A Constant Approximation Algorithm for Sorting Buffers
Jens S. Kohrt and Kirk Pruhs
203-211
Approximation Schemes for a Class of Subset Selection Problems
Kirk Pruhs and Gerhard J. Woeginger
212-221
Finding k-Connected Subgraphs with Minimum Average Weight
Prabhakar Gubbala and Balaji Raghavachari
222-231
On the (Im)possibility of Non-interactive Correlation Distillation
Ke Yang
232-241
Pure Future Local Temporal Logics Are Expressively Complete for Mazurkiewicz Traces
Volker Diekert and Paul Gastin
242-251
How Expressions Can Code for Automata
Sylvain Lombardy and Jacques Sakarovitch
252-261
Automata for Arithmetic Meyer Sets
Shigeki Akiyama, Frédérique Bassino and Christiane Frougny
2705
Efficiently Computing the Density of Regular Languages
Manuel Bodirsky, Tobias Gärtner, Timo von Oertzen and Jan Schwinghammer
271-278
Longest Repeats with a Block of Don’t Cares
Maxime Crochemore, Costas S. Iliopoulos, Manal Mohamed and Marie-France Sagot
279-291
Join Irreducible Pseudovarieties, Group Mapping, and Kovács-Newman Semigroups
John Rhodes and Benjamin Steinberg
292-301
Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank
Olivier Carton and Chloé Rispal
302-311
Expected Length of the Longest Common Subsequence for Large Alphabets
Marcos Kiwi, Martin Loebl and Jiří Matoušek
312-321
Universal Types and Simulation of Individual Sequences
Gadiel Seroussi
322-328
Separating Codes: Constructions and Bounds
Gérard Cohen and Hans Georg Schaathun
329-338
Encoding Homotopy of Paths in the Plane
Sergei Bespamyatnikh
339-348
A Unified Approach to Coding Labeled Trees
Saverio Caminiti, Irene Finocchi and Rossella Petreschi
2705
Cost-Optimal Trees for Ray Shooting
Hervé Brönnimann and Marc Glisse
359-368
Packing Problems with Orthogonal Rotations
Flavio Keidi Miyazawa and Yoshiko Wakabayashi
369-378
Combinatorial Problems on Strings with Applications to Protein Folding
Alantha Newman and Matthias Ruhl
379-390
Measurement Errors Make the Partial Digest Problem NP-Hard
Mark Cieliebak and Stephan Eidenbenz
391-400
Designing Small Keyboards Is Hard
Jean Cardinal and Stefan Langerman
401-412
Metric Structures in L1: Dimension, Snowflakes, and Average Distortion
James R. Lee, Manor Mendel and Assaf Naor
413-422
Nash Equilibria via Polynomial Equations
Richard J. Lipton and Evangelos Markakis
423-433
Minimum Latency Tours and the k-Traveling Repairmen Problem
Raja Jothi and Balaji Raghavachari
434-443
Server Scheduling in the Weighted ℓp Norm
Nikhil Bansal and Kirk Pruhs
444-454
An Improved Communication-Randomness Tradeoff
Martin Fürer
455-465
Distributed Games and Distributed Control for Asynchronous Systems
Paul Gastin, Benjamin Lerman and Marc Zeitoun
466-473
A Simplified and Dynamic Unified Structure
Mihai Bădoiu and Erik D. Demaine
474-487
Another View of the Gaussian Algorithm
Ali Akhavi and Céline Moreira Dos Santos
488-498
Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections
Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan
499-508
Rooted Maximum Agreement Supertrees
Jesper Jansson, Joseph H. -K. Ng, Kunihiko Sadakane and Wing-Kin Sung
509-518
Complexity of Cycle Length Modularity Problems in Graphs
Edith Hemaspaandra, Holger Spakowski and Mayur Thakur
519-529
Procedural Semantics for Fuzzy Disjunctive Programs on Residuated Lattices
Dušan Guller
530-539
A Proof System and a Decision Procedure for Equality Logic
Olga Tveretina and Hans Zantema
540-556
Approximating the Expressive Power of Logics in Finite Models
Argimiro Arratia and Carlos E. Ortiz
557-566
Arithmetic Circuits for Discrete Logarithms
Joachim von zur Gathen
567-576
On the Competitiveness of AIMD-TCP within a General Network
Jeff Edmonds
577-588
Gathering Non-oblivious Mobile Robots
Mark Cieliebak
589-598
Bisecting and Gossiping in Circulant Graphs
Bernard Mans and Igor Shparlinski
599-608
Multiple Mobile Agent Rendezvous in a Ring
Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Nicola Santoro and Cindy Sawchuk
2705
Global Synchronization in Sensornets
Jeremy Elson, Richard M. Karp, Christos H. Papadimitriou and Scott Shenker
Back matter