Schedule (Monday, 6th September)

8:30 - 9:00 Morning Coffee
09:00 - 9:50 Invited Speaker: Herbert Edelsbrunner
The Robustness of Level Sets
Mark de Berg
10:00 - 10:20 Coffee Break
10:20 - 12:00 Session 1a (ESA)
Prudence Wong
Session 1b (ESA)
Sergio Cabello
Session 1c (WABI)
Mona Singh
Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods
F. Eisenbrand, K. Kesavan, R. Mattikalli, M. Niemeier, A. Nordsieck, M. Skutella, J. Verschae and A. Wiese
Balancing Degree, Diameter and Weight in Euclidean Spanners
S. Solomon and M. Elkin
Improved Orientations of Physical Networks
I. Gamzu, D. Segev and R. Sharan
Non-clairvoyant Speed Scaling for Weighted Flow Time
S.-H. Chan, T.-W. Lam and L.-K. Lee
Testing Euclidean Spanners
F. Hellweg, M. Schmidt and C. Sohler
Enumerating Chemical Organisations in Consistent Metabolic Networks: Complexity and Algorithms
A. Marchetti-Spaccamela, M.-F. Sagot, L. Stougie and V. Lacroix
A Robust PTAS for Machine Covering and Packing
M. Skutella and J. Verschae
f-Sensitivity Distance Oracles and Routing Schemes
S. Chechik, M. Langberg, L. Roditty and D.Peleg
Efficient Subgraph Frequency Estimation with G-Tries
P. Ribeiro and F. Silva
Constructing the R* consensus tree of two trees in subcubic time
J. Jansson and W.-K. Sung
Identification of Rare Cell Populations in Comparative Flow Cytometry
A. Azad, J. Langguth, Y. Fang, A. Qi and A. Pothen
12:00 - 13:30 Lunch
13:30 - 14:45 Session 2a (ESA)
Mikko Koivisto
Session 2b (ESA)
Khaled Elbassioni
Session 2c (WABI)
Teresa Przytycka
Fast Minor Testing in Planar Graphs
I. Adler, F. Dorn, F.V. Fomin, I. Sau and D. Thilikos
Communication Complexity of Quasirandom Rumor Spreading
P. Berenbrink, R. Elsässer and T. Sauerwald
Sparsification of RNA Structure Prediction Including Pseudoknots
M. Mohl, R. Salari, S. Will, R. Backofen and S.C. Sahinalp
On the Number of Spanning Trees a Planar Graph Can Have
K. Buchin and A. Schulz
A complete characterization of group-strategy proof mechanisms of cost-sharing
E. Pountourakis and A. Vidali
Prediction of RNA secondary structure including kissing hairpin motifs
C. Theis, S. Janssen and R. Giegerich
Contractions of planar graphs in polynomial time
M. Kaminski, D. Paulusma and D. Thilikos
Contribution Games in Social Networks
E. Anshelevich and M. Hoefer
Reducing the Worst Case Running Time of a Family of RNA and CFG Problems, Using Valiant's Approach
S. Zakov D. Tsur and M. Ziv-Ukelson
14:45 - 15:05 Break
15:05 - 16:20 Session 3a (ESA)
Kevin Buchin
Session 3b (ESA)
Russell Martin
Session 3c (WABI)
Louxin Zhang
Improved Bounds for Online Stochastic Matching
B. Bahmani and M. Kapralov
Superselectors: Efficient Constructions and Applications
F. Cicalese and U. Vaccaro
A worst-case and practical speedup for the RNA co-folding problem using the Four-Russians idea
Y. Frid and D. Gusfield
Online Stochastic Packing applied to Display Ad Allocation
J. Feldman, M. Henzinger, N. Korula, V. Mirrokni and C. Stein
Estimating the Average of a Lipschitz-Continuous Function from One Sample
A. Das and D. Kempe
Sparse Estimation For Structural Variability
R. Hosur, R. Singh and B. Berger
Caching is Hard Even in the Fault Model
M. Chrobak, G. Woeginger, K. Makino and H. Xu
Streaming Graph Computations with a Helpful Advisor
J. Thaler, G. Cormode and M. Mitzenmacher
Effective Algorithms for Fusion Gene Detection
D. He and E. Eskin
16:20 - 16:40 Coffee Break
16:40 - 17:55 Session 4a (ESA)
Dan Halperin
Session 4b (ESA)
Ulrich Meyer
Session 4c (WABI)
Bernard Moret
Approximation Algorithms for Dominating Set in Disk Graphs
M. Gibson and I. Pirwani
n-Level Graph Partitioning
V. Osipov and P. Sanders
Reconstruction of Ancestral Genome subject to Whole Genome Duplication, Speciation, Rearrangement and Loss
D. Bertrand, Y. Gagnon, M. Blanchette and N. El-Mabrouk
Minimum Vertex Cover in Rectangle Graphs
R. Bar-Yehuda, D. Hermelin and D. Rawitz
Fast Routing in Very Large Public Transportation Networks Using Transfer Patterns
H. Bast, E. Carlsson, A. Eigenwillig, R. Geisberger, C. Harrelson, V. Raychev and F. Viger
Genomic distance with DCJ and indels
M.D.V. Braga, E. Willing and J. Stoye
Feedback Vertex Sets in Tournaments
S. Gaspers and M. Mnich
Finding the Diameter in Large Graphs: Experimentally turning a lower bound into an upper bound
P. Crescenzi, R. Grossi, C. Imbrenda, L. Lanzi and A. Marino
Listing All Sorting Reversals in Quadratic Time
K.M. Swenson, G. Badr and D. Sankoff
18:15 - 19:30 ESA Business meeting
18:15 - 19:30 WABI Poster Session