21. ESA 2013: Sophia Antipolis, France
- Hans L. Bodlaender, Giuseppe F. Italiano:
Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings. Lecture Notes in Computer Science 8125, Springer 2013, ISBN 978-3-642-40449-8 - Oswin Aichholzer, Wolfgang Mulzer, Alexander Pilz:
Flip Distance between Triangulations of a Simple Polygon is NP-Complete. 13-24 - Deepak Ajwani, Nodari Sitchinava:
Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures. 25-36 - Sander P. A. Alewijnse, Quirijn W. Bouts, Alex P. ten Brink, Kevin Buchin:
Computing the Greedy Spanner in Linear Space. 37-48 - Lars Arge, Gerth Stølting Brodal, Jakob Truelsen, Constantinos Tsirogiannis:
An Optimal and Practical Cache-Oblivious Algorithm for Computing Multiresolution Rasters. 61-72 - Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Paolo Penna, Giuseppe Persiano:
Logit Dynamics with Concurrent Updates for Local Interaction Games. 73-84 - Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe Francesco Italiano, Andrea Ribichini:
On Resilient Graph Spanners. 85-96 - Amotz Bar-Noy, Dror Rawitz, Peter Terlecky:
Maximizing Barrier Coverage Lifetime with Mobile Sensors. 97-108 - Jérémy Barbay, Ankur Gupta, Seungbum Jo, Srinivasa Rao Satti, Jonathan P. Sorenson:
Theory and Implementation of Online Multiselection Algorithms. 109-120 - Andreas Beckmann, Ulrich Meyer, David Veith:
An Implementation of I/O-Efficient Dynamic Breadth-First Search Using Level-Aligned Hierarchical Clustering. 121-132 - Djamal Belazzougui, Fabio Cunial, Juha Kärkkäinen, Veli Mäkinen:
Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform. 133-144 - Christoph Berkholz, Paul S. Bonsma, Martin Grohe:
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement. 145-156 - Davide Bilò, Luciano Gualà, Guido Proietti:
A Faster Computation of All the Best Swap Edges of a Shortest Paths Tree. 157-168 - Ivan Bliznets, Fedor V. Fomin, Michal Pilipczuk, Yngve Villanger:
Largest Chordal and Interval Subgraphs Faster Than 2 n. 193-204 - Prosenjit Bose, Jean-Lou De Carufel, Stephane Durocher:
Revisiting the Problem of Searching on a Line. 205-216 - Jop Briët, Daniel Dadush, Sebastian Pokutta:
On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity. 217-228 - Gerth Stølting Brodal, Andrej Brodnik, Pooya Davoodi:
The Encoding Complexity of Two Dimensional Range Minimum Data Structures. 229-240 - Kevin Buchin, Maike Buchin, Rolf van Leusden, Wouter Meulemans, Wolfgang Mulzer:
Computing the Fréchet Distance with a Retractable Leash. 241-252 - Kevin Buchin, Olivier Devillers, Wolfgang Mulzer, Okke Schrijvers, Jonathan Richard Shewchuk:
Vertex Deletion for 3D Delaunay Triangulations. 253-264 - Ioannis Caragiannis, Christos Kaklamanis, Maria Kyropoulou:
Limitations of Deterministic Auction Design for Correlated Bidders. 277-288 - Deepesh Agarwal, Júlio César Silva Araújo, Christelle Caillouet, Frédéric Cazals, David Coudert, Stéphane Pérennes:
Connectivity Inference in Mass Spectrometry Based Structure Determination. 289-300 - Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg:
Secluded Connectivity Problems. 301-312 - Rajesh Hemant Chitnis, László Egri, Dániel Marx:
List H-Coloring a Graph by Removing Few Vertices. 313-324 - Andrea E. F. Clementi, Pierluigi Crescenzi, Carola Doerr, Pierre Fraigniaud, Marco Isopi, Alessandro Panconesi, Francesco Pasquale, Riccardo Silvestri:
Rumor Spreading in Random Evolving Graphs. 325-336 - Michael S. Crouch, Andrew McGregor, Daniel Stubbs:
Dynamic Graphs in the Sliding-Window Model. 337-348 - Radu Curticapean, Marvin Künnemann:
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems. 349-360 - Marek Cygan, Fabrizio Grandoni, Danny Hermelin:
Tight Kernel Bounds for Problems on Graphs with Small Degeneracy - (Extended Abstract). 361-372 - Mark de Berg, Dirk H. P. Gerrits:
Labeling Moving Points with a Trade-Off between Label Speed and Label Overlap. 373-384 - Bart de Keijzer, Evangelos Markakis, Guido Schäfer, Orestis Telelis:
Inefficiency of Standard Multi-unit Auctions. 385-396 - Wolfgang Dvorák, Monika Henzinger, David P. Williamson:
Maximizing a Submodular Function with Viability Constraints. 409-420 - William S. Evans, Stefan Felsner, Michael Kaufmann, Stephen G. Kobourov, Debajyoti Mondal, Rahnuma Islam Nishat, Kevin Verbeek:
Table Cartograms. 421-432 - Linda Farczadi, Konstantinos Georgiou, Jochen Könemann:
Network Bargaining with General Capacities. 433-444 - Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, Hadas Shachnai:
Tractable Parameterizations for the Minimum Linear Arrangement Problem. 457-468 - Hendrik Fichtenberger, Marc Gillé, Melanie Schmidt, Chris Schwiegelshohn, Christian Sohler:
BICO: BIRCH Meets Coresets for k-Means Clustering. 481-492 - Fedor V. Fomin, Michal Pilipczuk:
Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph. 505-516 - Travis Gagie, Danny Hermelin, Gad M. Landau, Oren Weimann:
Binary Jumbled Pattern Matching on Trees and Tree-Like Structures. 517-528 - Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar:
Kernelization Using Structural Parameters on Sparse Graph Classes. 529-540 - Panos Giannopoulos, Christian Knauer, Daniel Werner:
On the Computational Complexity of Erdős-Szekeres and Related Problems in ℝ3. 541-552 - Roberto Grossi, John Iacono, Gonzalo Navarro, Rajeev Raman, Srinivasa Rao Satti:
Encodings for Range Selection and Top-k Queries. 553-564 - Nir Halman, Giacomo Nannicini, James B. Orlin:
A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs. 577-588 - Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking:
An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. 589-600 - Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter:
Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet. 625-636 - Jochen Könemann, Sina Sadeghian Sadeghabad, Laura Sanità:
Better Approximation Algorithms for Technology Diffusion. 637-646 - Stefan Kratsch:
On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility. 647-658 - Mark Jones, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, Ondrej Suchý:
Parameterized Complexity of Directed Steiner Tree on Sparse Graphs. 671-682 - Pasin Manurangsi, Dana Moshkovitz:
Improved Approximation Algorithms for Projection Games - (Extended Abstract). 683-694 - Jean-Daniel Boissonnat, Tamal K. Dey, Clément Maria:
The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology. 695-706 - Jannik Matuschke, Andreas Bley, Benjamin Müller:
Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections. 707-718 - George B. Mertzios:
The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial. 719-730 - Shin-ichi Minato:
Z-Skip-Links for Fast Traversal of ZDDs Representing Large-Scale Sparse Datasets. 731-742 - Nguyen Kim Thang:
Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling. 755-766 - Subhash Suri, Kevin Verbeek, Hakan Yildiz:
On the Most Likely Convex Hull of Uncertain Points. 791-802 - Rahul Shah, Cheng Sheng, Sharma V. Thankachan, Jeffrey Scott Vitter:
Top-k Document Retrieval in External Memory. 803-814 - Kai Xiao, Danny Ziyi Chen, Xiaobo Sharon Hu, Bo Zhou:
Shell: A Spatial Decomposition Data Structure for 3D Curve Traversal on Many-Core Architectures. 815-826