19:00: Welcoming reception by the City of Bergen in Håkon's Hall.
| ESA 1 | ESA 2 | WABI | WAOA | IWPEC | |
|---|---|---|---|---|---|
| 8:30 | Opening speeches | ||||
| 9:00 |
Plenary invited speech:
Monika Henzinger Algorithmic Aspects of Web Search Engines |
||||
| 9:50 | Short break | ||||
| 10:00 | Fast sparse matrix multiplication Raphael Yuster, Uri Zwick |
Solving Geometric Covering Problems by Data Reduction Steffen Mecke, Dorothea Wagner |
Reversing Gene Erosion - Reconstructing Ancestral Bacterial Genomes from Gene-Content and Gene Order Data Joel V. Earnest-DeYoung, Emmanuelle Lerat, Bernard M.E. Moret |
WAOA invited speech: Yossi Azar Online packet switching - techniques and algorithms |
IWPEC invited speech: Mike Langston Practical FPT Implementations and Applications |
| 10:25 | Maximum Matching in Planar Graphs via Gaussian Elimination Marcin Mucha, Piotr Sankowski |
An Experimental Study of Random Knapsack Problems Rene Beier, Berthold Voecking |
Reconstructing Ancestral Gene Orders Using Conserved Intervals Anne Bergeron, Mathieu Blanchette, Annie Chateau, Cedric Chauve |
||
| 10:50 | Coffee break | ||||
| 11:15 | Approximate Unions of Lines and Minkowski Sums Marc van Kreveld, A. Frank van der Stappen |
Swap and Mismatch Edit Distance Amihood Amir, Estrella Eisenberg, Ely Porat |
Sorting By Reversals with Common Intervals Figeac Martin, Varre Jean-Stephane |
Improved bounds for sum multicoloring and weighted completion time of dependent jobs Rajiv Gandhi, Magnus Halldorsson, Guy Kortsarz, Hadas Shachnai |
Computing Small Search Numbers in Linear Time Hans Bodlaender, Dimitrios Thilikos |
| 11:40 | Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Hai Yu |
Approximate Parameterized Matching Carmit Hazay, Moshe Lewenstein, Dina Sokol |
A Polynomial-Time Algorithm for the Matching of Crossing Contact-Map Patterns Jens Gramm |
Minimum Sum Multicoloring on the Edges of Planar Graphs and Partial k-trees Daniel Marx |
Online Problems, Pathwidth, and Persistence Rodney Downey, Catherine McCartin |
| 12:05 | Optimal External-Memory Planar Point Enclosure Lars Arge, Vasilis Samoladas, Ke Yi |
An Algorithm for Computing DNA Walks Ankur Bhargava, S. Rao Kosaraju |
A 1.5-Approximation Algorithm for Sorting by Transpositions and Transreversals Tzvika Hartman, Roded Sharan |
Strong Colorings of Hypergraphs Geir Agnarsson, Magnus Halldorsson |
Parameterized Graph Separation Problems Daniel Marx |
| 12:30 | Lunch | ||||
| 14:00 | Direct Routing: Algorithms and Complexity Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, Paul Spirakis |
Labeling Smart Dust Vikas Bansal, Friedhelm Meyer auf der Heide, Christian Sohler |
Algorithms for finding maximal-scoring segment sets Miklos Csuros |
Ordering-Preserving Transformations and Greedy-like Algorithms Spyros Angelopoulos |
Compatibility of Unrooted Phylogenetic Trees is FPT David Bryant, Jens Lagergren |
| 14:25 | Path Decomposition under a New Cost Measure with Applications to Optical Network Design Elliot Anshelevich, Lisa Zhang |
On Rectangular Cartograms Marc van Kreveld, Bettina Speckmann |
Gapped Local Similarity Search with Provable Guarantees Manikandan Narayanan, Richard Karp |
Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints H. Shachnai, O. Shmueli, R. Sayegh |
Perfect Path Phylogeny Haplotyping with Missing Data is Fixed-Parameter Tractable Jens Gramm, Till Nierhoff, Till Tantau |
| 14:50 | Time Dependent Multi Scheduling of Multicast Rami Cohen, Dror Rawitz, Danny Raz |
A Straight Skeleton Approximating the Medial Axis Mirela Tanase, Remco C. Veltkamp |
Monotone Scoring of Patterns with Mismatches Alberto Apostolico, Cinzia Pizzi |
Universal Bufferless Routing Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas |
Parameterized Enumeration, Transversals, and Phylogeny Reconstruction Peter Damaschke |
| 15:15 | Coffee break | ||||
| 15:45 | Dynamic Shannon Coding Travis Gagie |
Stable Minimum Storage Merging by Symmetric Comparisons Pok-Son Kim, Arne Kutzner |
Suboptimal local alignments across multiple scoring schemes Morris Michael, Christoph Dieterich, Jens Stoye |
A 5/4-approximation algorithm for biconnecting a graph with a given Hamiltonian path Davide Bilo, Guido Proietti |
Refined Memorisation for Vertex Cover L. Sunil Chandran, Fabrizio Grandoni |
| 16:10 | On the Stability of Multiple Partner Stable Marriages with Ties Marun S. Malhotra |
Beyond Optimal Play in Two-Person-Zerosum Games Ulf Lorenz |
A faster reliable algorithm to estimate the p-value of the multinomial llr statistic Uri Keich, Niranjan Nagarajan |
Approximating directed multicuts Yana Kortsarts, Guy Kortsarz, Zeev Nutov |
Greedy Localization, Iterative Compression and Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for SET SPLITTING and a Novel 2k Kernelization for VERTEX COVER Frank Dehne, Michael Fellows, Frances Rosamond, Peter Shaw |
| 16:35 | Short break | ||||
| 16:45 | Business meeting | ||||
| ESA 1 | ESA 2 | WABI | WAOA | IWPEC | |
|---|---|---|---|---|---|
| 9:00 |
Plenary invited speech:
Mike Fellows A Survey of FPT Algorithm Design Techniques with an Emphasis on Recent Advances and Connections to Practical Computing |
||||
| 9:50 | Short break | ||||
| 10:00 | On Dynamic Shortest Paths Problems Liam Roditty, Uri Zwick |
Adding Hidden Nodes to Gene Networks. Tamir Tuller, Benny Chor |
Priority Algorithms for Graph Optimization Problems A. Borodin, J. Boyar, K. S. Larsen |
IWPEC invited speech: Gerhard Woeginger Space and time complexity of exact algorithms: Some open problems |
|
| 10:25 | Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems Reuven Cohen, David Peleg |
Non-additive Shortest Paths George Tsaggouris, Christos Zaroliagis |
Joint Analysis of DNA Copy Numbers and Expression Levels Doron Lipson, Amir Ben-Dor, Elinor Dehan, Zohar Yakhini |
Online bin packing with resource augmentation Leah Epstein, Rob van Stee |
|
| 10:50 | Coffee break | ||||
| 11:15 | On the Evolution of Selfish Routing Simon Fischer, Berthold Voecking |
Multi-word Atomic Read/Write Registers on Multiprocessor Systems Andreas Larsson, Anders Gidenstam, Phuong H. Ha, Marina Papatriantafilou, Philippas Tsigas |
Searching for Regulatory Elements of Alternative Splicing Events Using Phylogenetic Footprinting Daichi Shigemizu, Osamu Maruyama |
This side up! Leah Epstein, Rob van Stee |
On Miniaturized Problems in Parameterized Complexity Theory Yijia Chen, Joerg Flum |
| 11:40 | Fisher Equilibrium Price with a Class of Concave Utility Functions Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao |
Data Migration on Parallel Disks Leana Golubchik, Samir Khuller, Yoo-Ah Kim, Svetlana Shargorodskaya, Yung-Chun (Justin) Wan |
Supervised learning-aided optimization of expert-driven functional protein sequence annotation Lev Soinov, Alexander Kanapin, Misha Kapushesky |
Approximation Algorithms for Spreading Points Sergio Cabello |
Bounded Fixed-Parameter Tractability: The Case 2poly(k) Mark Weyer |
| 12:05 | Efficient IP Table Lookup via Adaptive Stratified Trees with Selective Reconstructions Marco Pellegrini, Giordano Fusco |
Multiple vector seeds for protein alignment Daniel Brown |
Submodular Integer Cover and its Application to Production Planning T. Fujito, T. Yabuta |
Simplifying the Weft Hierarchy Jonathan Buss, Tarique Islam |
|
| 12:30 | Lunch | ||||
| 14:00 | Maximizing Throughput in Multi-Queue Switches Yossi Azar, Arik Litichevskey |
Finding Dominators in Practice Loukas Georgiadis, Renato F. Werneck, Robert E. Tarjan, Spyridon Triantafyllis, David August |
Solving the protein threading problem by lagrangian relaxation Stefan Balev |
Joint Base Station Scheduling T. Erlebach, R. Jacob, M. Mihalak, M. Nunkesser, G. Szabo, P. Widmayer |
Moving Policies in Cyclic Assembly-Line Scheduling Matthias Mueller-Hannemann, Karsten Weihe |
| 14:25 | Improved Online Algorithms for Buffer Management in QoS Switches Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomas Tichy |
Construction of Minimum-Weight Spanners Mikkel Sigurd, Martin Zachariasen |
Protein-Protein Interfaces: Recognition of Similar Spatial and Chemical Organizations Alexandra Shulman-Peleg, Shira Mintz, Ruth Nussinov, Haim Wolfson |
Deterministic Monotone Algortihms for Scheduling on Related Machines P. Ambrosio, V. Auletta |
Chordless Paths Through Three Vertices Michael Hoffmann, Robert Haas |
| 14:50 | An Improved Algorithm for CIOQ Switches Y. Azar, Y. Richter |
Contraction and Treewidth Lower Bounds Hans L. Bodlaender, Arie M. C. A. Koster, Thomas Wolle |
ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences Stanislav Angelov, Sanjeev Khanna, Li Li, Fernando Pereira |
Stochastic Online Scheduling on Parallel Machines N. Megow, M. Uetz, T. Vredeveld |
Parameterized Coloring Problems on Chordal Graphs Daniel Marx |
| 15:15 | Coffee break | ||||
| 15:45 | Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families Douglas E. Carroll, Ashish Goel |
An Inductive Construction for Plane Laman Graphs via Vertex Splitting Zsolt Fekete, Tibor Jordan, Walter Whiteley |
Local Search Heuristic for Rigid Protein Docking Vicky Choi, Pankaj Agarwal, Herbert Edelsbrunner, Johannes Rudolph |
More Powerful and Simpler Cost-Sharing Methods P. Penna, C. Ventre |
On Decidability of MSO Theories of Representable Matroids Petr Hlineny, Detlef Seese |
| 16:10 | Graph Decomposition Lemmas and Their Role in Metric Embedding Methods Yair Bartal |
Fast 3-coloring Triangle-Free Planar Graphs Lukasz Kowalik |
Translation Initiation Sites Prediction with mixture Gaussian models Guoliang Li, Tze-Yun Leong, Louxin Zhang |
Pricing Network Edges to Cross a River A. Grigoriev, S. van Hoesel, A. F. van der Kraaij, M. Uetz, M. Bouhtou |
On Finding Short Resolution Refutations and Small Unsatisfiable Subsets Michael Fellows, Stefan Szeider, Graham Wrightson |
| 16:35 | Short break | ||||
| 16:45 | Business meeting | ||||
| 19:00 | Conference dinner (funicular departure 18:30) |
||||
| ESA 1 | ESA 2 | WABI | WAOA | IWPEC | |
|---|---|---|---|---|---|
| 9:00 |
Plenary invited speech:
Marie-France Sagot Some questions around genome rearrangements |
||||
| 9:50 | Short break | ||||
| 10:00 | Hardness and Approximation Results for Packing Steiner Trees Joseph Cheriyan, Mohammad R. Salavatipour |
Extreme Points under Random Noise Valentina Damerow, Christian Sohler |
Linear Reduction for Haplotype Inference Jingwu He, Alex Zelikovsky |
WAOA invited speech: Klaus Jansen Approximation algorithms for mixed fractional packing and covering problems |
A Structural View on Parameterizing Problems: Distance from Triviality Jiong Guo, Falk Hüffner, Rolf Niedermeier |
| 10:25 | Approximation Algorithms for Quickest Spanning Tree Problems Refael Hassin, Asaf Levin |
Seeking a Vertex of the Planar Matching Polytope in NC Raghav Kulkarni, Meena Mahajan |
A new integer programming formulation for the pure parsimony problem in haplotype analysis Daniel Brown, Ian Harrower |
The Minimum Weight Triangulation Problem with Few Inner Points Michael Hoffmann, Yoshio Okamoto |
|
| 10:50 | Coffee break | ||||
| 11:15 | Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries Naveen Garg, Rohit Khandekar |
On Adaptive Integer Sorting Anna Pagh, Rasmus Pagh, Mikkel Thorup |
Fast Hare: a Fast Heuristic for Single Individual SNP Haplotype Reconstruction Alessandro Panconesi, Mauro Sozio |
A PTAS for Delay Minimization in Establishing Wireless Conference Calls Leah Epstein, Asaf Levin |
Looking at the Stars Elena Prieto, Christian Sloper |
| 11:40 | Flows on Few Paths: Algorithms and Lower Bounds Maren Martens, Martin Skutella |
The Average Case Analysis of Partition Sorts Richard Cole, David C. Kandathil |
Approximation Algorithms for the Selection of Robust Tag SNPs Yao-Ting Huang, Kui Zhang, Ting Chen, Kun-Mao Chao |
Off-line Admission Control for Advance Reservations in Star Networks U. Adamy, T. Erlebach, D. Mitsche, I. Schurr, B. Speckmann, E. Welzl |
Smaller Kernels for Hitting Set Problems of Constant Arity Naomi Nishimura, Prabhakar Ragde, Dimitrios Thilikos |
| 12:05 | Incremental Algorithms for Facility Location and k-Median Dimitris Fotakis |
Super Scalar Sample Sort Peter Sanders, Sebastian Winkel |
The Minisatellite Transformation Problem Revisited: A Run Length Encoded Approach Behshad Behzadi, Jean-Marc Steyaert |
Better bounds for minimizing SONET ADMs Leah Epstein, Asaf Levin |
Packing Edge Disjoint Triangles: A Parameterized View Luke Mathieson, Elena Prieto, Peter Shaw |
| 12:30 | Lunch | ||||
| 14:00 | Code Flexibility and Program Efficiency by Genericity: Improving Cgal's Arrangements Efi Fogel, Ron Wein, Dan Halperin |
Modeling Locality: A Probabilistic Analysis of LRU and FWF Luca Becchetti |
A Faster and More Space-Efficient Algorithm for Inferring Arc-Annotations of RNA Sequences through Alignment Jesper Jansson, See-Kiong Ng, Wing-Kin Sung, Willy Hugo |
A Direct Algorithm for the Parameterized Face Cover Problem Faisal Abu-Khzam, Mike Langston |
|
| 14:25 | Classroom Examples of Robustness Problems in Geometric Computations Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap |
On Variable-Sized Multidimensional Packing Leah Epstein, Rob van Stee |
New Algorithms for Multiple DNA Sequence Alignment Daniel G. Brown, Alexander K. Hudek |
Parameterized Algorithms for Feedback Vertex Set Iyad Kanj, Michael Pelsmajer, Marcus Schaefer |
|
| 14:50 | Comparing real algebraic numbers of small degree Ioannis Z. Emiris, Elias Tsigaridas |
Competitive Online Approximation of the Optimal Search Ratio Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen |
Chaining algorithms for alignment of draft sequence Michael Brudno, Mukund Sundararajanan, Serafim Batzoglou |
Improved Parameterized Algorithms for Feedback Set Problems in Weighted Tournaments Venkatesh Raman, Saket Saurabh |
|
| 15:15 | Coffee break | ||||
| 15:45 |
Plenary invited speech:
Leo Kroon Railway Optimization: An overview |
||||
| 16:35 | Short break | ||||
| 16:40 | Business meeting | Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms Sergey Fedin, Alexander Kulikov |
|||
| 17:05 | |||||
| ESA 1 | ESA 2 | WABI | ATMOS | |
|---|---|---|---|---|
| 9:00 |
Plenary invited speech:
David Eppstein Quasiconvex Programming |
|||
| 9:50 | Short break | |||
| 10:00 | Uniform Algorithms for Deterministic Construction of Efficient Dictionaries Milan Ruzic |
An Approximation Algorithm for Maximum Triangle Packing Refael Hassin, Shlomi Rubinstein |
Online Consensus and Agreement of Phylogenetic Trees Tanya Y. Berger-Wolf |
Platform Assignment Sabine Cornelsen, Gabriele Di Stefano |
| 10:25 | Fast Multipoint Evaluation of Bivariate Polynomials Michael Nüsken, Martin Ziegler |
Approximation Hardness of Dominating Set Problems Miroslav Chlebik, Janka Chlebikova |
Relation of residues in the variable region of 16S rDNA sequences and their relevance to genus-specificity Maciej Liskiewicz, Hemant Purohit, Dhananjay Raje |
Rotation Planning of locomotives and carriage groups with shared capacities Taieb Mellouli, Leena Suhl |
| 10:50 | Coffee break | |||
| 11:15 | Load Balancing of Indivisible Unit Size Tokens in Dynamic and Heterogeneous Network Robert Elsaesser, Burkhard Monien, Stefan Schamberger |
Faster Fixed-Parameter Tractable Algorithms for Matching and Packing problems M.R. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, D.M. Thilikos, S. Whitesides |
Topological Rearrangements and Local Search Method for Tandem Duplication Trees Denis Bertrand, Olivier Gascuel |
Finding All Attractive Train Connections by Multi-Criteria Pareto Search Matthias Müller-Hannemann, Mathias Schnee |
| 11:40 | Radio Network Clustering from Scratch Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer |
A Parameterized Algorithm for Upward Planarity Testing Hubert Chan |
Phylogenetic Super-Networks from Partial Trees Daniel Huson, Tobias Dezulian, Tobias Klöpper, Mike Steel |
The Railway Traveling Salesman Problem Georgia Hadjicharalambous, Petrica Pop, Evangelia Pyrga, George Tsaggouris, Christos Zaroliagis |
| 12:05 | Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors Junning Liu, Micah Adler |
Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings Josep Diaz, Maria Serna, Dimitrios M. Thilikos |
Phylogeny by Hybridization Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim, Li-San Wang |
An integrated Methodology for the rapid transit network design Gilbert Laporte, Alfredo Marin, Juan Antonio Mesa, Francisco Ortega |
| 12:30 | Lunch | |||
| 14:00 | A Fast Distributed Algorithm for Approximating the Maximum Matching Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymanska |
Approximation of Rectangle Stabbing and Interval Stabbing problems Sofia Kovaleva, Frits Spieksma |
Novel tree edit operations for RNA secondary structure comparison Julien Allali, Marie-France Sagot |
Fare integration in regional transit services Domenico Gattuso, Giuseppe Musolino |
| 14:25 | Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems E. Boros, E. Elbassioni, V. Gurvich |
Tiling a Polygon with Two Kinds of Rectangles Eric Remila |
The Most Probable Labeling Problem in HMMs and Its Application to Bioinformatics Brona Brejova, Daniel G. Brown, Tomas Vinar |
Intelligent Train scheduling on a High-Loaded Railway Network Antonio Lova, Pilar Tormos, Federico Barber, Laura Ingolotti, Miguel A. Salido, Montserrat Abril |
| 14:50 | Equivalence of Search Capability among Mobile Guards with Various Visibilities Jae-Ha Lee, Sang-Min Park, Kyung-Yong Chwa |
Integrating Sample-driven and Pattern-driven Approaches in Motif Finding Sing-Hoi Sze, Songjian Lu, Jianer Chen |
On-Line Delay Management on a Single Transit Line Michael Gatto, Riko Jacob, Leon Peeters, Peter Widmayer |
|
| 15:15 | Coffee break | |||
| 15:45 | Finding Optimal Pairs of Patterns Hideo Bannai, Heikki Hyyro, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai, Satoru Miyano |
An estimate of the punctuality benefits of automatic operational train sequencing Maarten Bartholomeus, Rien Gouweloos |
||
| 16:10 | Finding missing patterns Shunsuke Inenaga, Teemu Kivioja, Veli Mäkinen |
Business meeting | ||
| 16:35 | ||||