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 | ||
