![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
24. ESA 2016: Aarhus, Denmark
- Piotr Sankowski, Christos D. Zaroliagis:
24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark. LIPIcs 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2016, ISBN 978-3-95977-015-6 - Front Matter, Table of Contents, Preface, Programm Commitee, External Reviewers. 0:i-0:xxiv
Invited Papers
- Loukas Georgiadis
, Giuseppe F. Italiano, Nikos Parotsidis
:
2-Connectivity in Directed Graphs. 1:1-1:14 - Ola Svensson:
Algorithms with Provable Guarantees for Clustering. 2:1-2:1
Regular Papers
- Melika Abolhassani, T.-H. Hubert Chan, Fei Chen, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Hamid Mahini, Xiaowei Wu
:
Beating Ratio 0.5 for Weighted Oblivious Matching Problems. 3:1-3:18 - Mikkel Abrahamsen
, Bartosz Walczak:
Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace. 4:1-4:15 - Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Ely Porat:
Sublinear Distance Labeling. 5:1-5:15 - Tobias Arndt, Danijar Hafner, Thomas Kellermeier, Simon Krogmann
, Armin Razmjou, Martin S. Krejca, Ralf Rothenberger
, Tobias Friedrich:
Probabilistic Routing for On-Street Parking Search. 6:1-6:13 - Moritz Baum, Thomas Bläsius
, Andreas Gemsa, Ignaz Rutter
, Franziska Wegner:
Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths. 7:1-7:18 - Xiaohui Bei
, Jugal Garg, Martin Hoefer, Kurt Mehlhorn:
Computing Equilibria in Markets with Budget-Additive Utilities. 8:1-8:14 - Huck Bennett, Daniel Dadush, Noah Stephens-Davidowitz:
On the Lattice Distortion Problem. 9:1-9:17 - Petra Berenbrink, Tom Friedetzky
, Peter Kling
, Frederik Mallmann-Trenn, Chris Wastell:
Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing. 10:1-10:18 - Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket:
On the Hardness of Learning Sparse Parities. 11:1-11:17 - Marcin Bienkowski
, Martin Böhm
, Jaroslaw Byrka
, Marek Chrobak, Christoph Dürr, Lukás Folwarczný
, Lukasz Jez, Jiri Sgall
, Kim Thang Nguyen, Pavel Veselý
:
Online Algorithms for Multi-Level Aggregation. 12:1-12:17 - Davide Bilò
, Luciano Gualà, Stefano Leucci
, Guido Proietti
:
Compact and Fast Sensitivity Oracles for Single-Source Distances. 13:1-13:14 - Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Yan Gu
, Julian Shun:
Efficient Algorithms with Asymmetric Read and Write Costs. 14:1-14:18 - Thomas Bläsius, Tobias Friedrich, Anton Krohmer:
Hyperbolic Random Graphs: Separators and Treewidth. 15:1-15:16 - Thomas Bläsius, Tobias Friedrich, Anton Krohmer, Sören Laue:
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. 16:1-16:18 - Greg Bodwin, Sebastian Krinninger
:
Fully Dynamic Spanners with Worst-Case Update Time. 17:1-17:18 - Édouard Bonnet, László Egri, Dániel Marx:
Fixed-Parameter Approximability of Boolean MinCSPs. 18:1-18:18 - Édouard Bonnet, Tillmann Miltzow:
Parameterized Hardness of Art Gallery Problems. 19:1-19:17 - Michele Borassi, Emanuele Natale
:
KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. 20:1-20:18 - Ralf Borndörfer, Heide Hoppmann, Marika Karbstein:
Separation of Cycle Inequalities for the Periodic Timetabling Problem. 21:1-21:13 - Quirijn W. Bouts, Irina Kostitsyna
, Marc J. van Kreveld
, Wouter Meulemans, Willem Sonke
, Kevin Verbeek
:
Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. 22:1-22:16 - Karl Bringmann, László Kozma
, Shay Moran, N. S. Narayanaswamy:
Hitting Set for Hypergraphs of Low VC-dimension. 23:1-23:18 - Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, Pan Xu:
New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching. 24:1-24:16 - Jean Cardinal, John Iacono
, Aurélien Ooms:
Solving k-SUM Using Few Linear Queries. 25:1-25:17 - Cameron T. Chalk, Eric Martinez, Robert T. Schweller, Luis Vega, Andrew Winslow, Tim Wylie:
Optimal Staged Self-Assembly of General Shapes. 26:1-26:17 - Erin W. Chambers
, Irina Kostitsyna
, Maarten Löffler, Frank Staals:
Homotopy Measures for Representative Trajectories. 27:1-27:17 - Krishnendu Chatterjee
, Rasmus Ibsen-Jensen, Andreas Pavlogiannis
:
Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs. 28:1-28:17 - Markus Chimani, Tilo Wiedera:
An ILP-based Proof System for the Crossing Number Problem. 29:1-29:13 - George Christodoulou
, Martin Gairing, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis:
Strategic Contention Resolution with Limited Feedback. 30:1-30:16 - Raphaël Clifford, Markus Jalsenius, Benjamin Sach:
Cell-Probe Lower Bounds for Bit Stream Computation. 31:1-31:15 - Michael S. Crouch
, Andrew McGregor, Gregory Valiant, David P. Woodruff:
Stochastic Streams: Sample Complexity vs. Space Complexity. 32:1-32:15 - Radu Curticapean:
Counting Matchings with k Unmatched Vertices in Planar Graphs. 33:1-33:17 - Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen
, Marcel Roeloffzen, Shakhar Smorodinsky
:
On Interference Among Moving Sensors and Related Problems. 34:1-34:11 - Tamal K. Dey, Dayu Shi, Yusu Wang:
SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse. 35:1-35:16 - Andrew Drucker, Jesper Nederlof, Rahul Santhanam:
Exponential Time Paradigms Through the Polynomial Time Lens. 36:1-36:14 - Christoph Dürr, Christian Konrad, Marc P. Renault:
On the Power of Advice and Randomization for Online Bipartite Matching. 37:1-37:16 - Stefan Edelkamp
, Armin Weiß
:
BlockQuicksort: Avoiding Branch Mispredictions in Quicksort. 38:1-38:16 - Eduard Eiben, Robert Ganian, Kustaa Kangas, Sebastian Ordyniak
:
Counting Linear Extensions: Parameterizations by Treewidth. 39:1-39:18 - Guy Even, Moti Medina
, Adi Rosén:
A Constant Approximation Algorithm for Scheduling Packets on Line Networks. 40:1-40:16 - Moran Feldman
, Moshe Tennenholtz, Omri Weinstein:
Distributed Signaling Games. 41:1-41:16 - Krzysztof Fleszar, Matthias Mnich
, Joachim Spoerhase
:
New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness. 42:1-42:17 - Nathanaël François, Frédéric Magniez, Michel de Rougemont, Olivier Serre:
Streaming Property Testing of Visibly Pushdown Languages. 43:1-43:17 - Shay Golan
, Tsvi Kopelowitz, Ely Porat:
Streaming Pattern Matching with d Wildcards. 44:1-44:16 - Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, Ely Porat:
How Hard is it to Find (Honest) Witnesses?. 45:1-45:16 - Gramoz Goranci, Monika Henzinger, Mikkel Thorup
:
Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time. 46:1-46:17 - Sathish Govindarajan, Rajiv Raman, Saurabh Ray, Aniket Basu Roy
:
Packing and Covering with Non-Piercing Regions. 47:1-47:17 - Monika Henzinger, Stefan Neumann
:
Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning. 48:1-48:11 - Chien-Chung Huang, Sebastian Ott:
A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges. 49:1-49:15 - Lingxiao Huang
, Jian Li, Jeff M. Phillips, Haitao Wang:
epsilon-Kernel Coresets for Stochastic Points. 50:1-50:18 - Hiro Ito:
Every Property Is Testable on a Natural Class of Scale-Free Multigraphs. 51:1-51:12 - Matti Karppa
, Petteri Kaski, Jukka Kohonen, Padraig Ó Catháin
:
Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time. 52:1-52:17 - Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, Mikkel Thorup
:
Faster Worst Case Deterministic Dynamic Connectivity. 53:1-53:15 - Thomas Kesselheim, Andreas Tönnis
:
Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions. 54:1-54:17 - Subhash Khot, Rishi Saket:
Hardness of Bipartite Expansion. 55:1-55:17 - Lasse Kliemann, Christian Schielke, Anand Srivastav:
A Streaming Algorithm for the Undirected Longest Path Problem. 56:1-56:17 - Pavel Kolev, Kurt Mehlhorn:
A Note On Spectral Clustering. 57:1-57:14 - Lukasz Kowalik
, Juho Lauri, Arkadiusz Socala:
On the Fine-Grained Complexity of Rainbow Coloring. 58:1-58:16 - Stefan Kratsch:
A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. 59:1-59:17 - Adam Kunysz:
The Strongly Stable Roommates Problem. 60:1-60:15 - Juha Kärkkäinen, Dominik Kempa
:
Faster External Memory LCP Array Construction. 61:1-61:16 - Jian Li, Wei Zhan:
Almost All Even Yao-Yao Graphs Are Spanners. 62:1-62:13 - Giorgio Lucarelli
, Kim Thang Nguyen, Abhinav Srivastav, Denis Trystram:
Online Non-Preemptive Scheduling in a Resource Augmentation Model Based on Duality. 63:1-63:17 - Clément Maria, Jonathan Spreer
:
Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants. 64:1-64:16 - Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Sadra Yazdanbod:
The Computational Complexity of Genetic Diversity. 65:1-65:17 - Tillmann Miltzow, Lothar Narins, Yoshio Okamoto
, Günter Rote, Antonis Thomas, Takeaki Uno:
Approximation and Hardness of Token Swapping. 66:1-66:15 - Matthias Mnich
, Virginia Vassilevska Williams, László A. Végh
:
A 7/3-Approximation for Feedback Vertex Sets in Tournaments. 67:1-67:14 - Riley Murray, Megan Chao, Samir Khuller:
Scheduling Distributed Clusters of Parallel Machines: Primal-Dual and LP-based Approximation Algorithms. 68:1-68:17 - Jesper Nederlof:
Finding Large Set Covers Faster via the Representation Method. 69:1-69:15 - Daniel Neuen
:
Graph Isomorphism for Unit Square Graphs. 70:1-70:17 - Alantha Newman, Heiko Röglin
, Johanna Seif:
The Alternating Stock Size Problem and the Gasoline Puzzle. 71:1-71:16 - Ely Porat, Eduard Shahbazian, Roei Tov:
New Parameterized Algorithms for APSP in Directed Graphs. 72:1-72:13 - Dror Rawitz, Adi Rosén:
Online Budgeted Maximum Coverage. 73:1-73:17 - Andreas S. Schulz, José Verschae:
Min-Sum Scheduling Under Precedence Constraints. 74:1-74:13 - Chris Schwiegelshohn, Uwe Schwiegelshohn:
The Power of Migration for Online Slack Scheduling. 75:1-75:17 - Kiril Solovey, Dan Halperin:
Sampling-Based Bottleneck Pathfinding with Applications to Fréchet Matching. 76:1-76:16 - Haitao Wang:
On the Geodesic Centers of Polygonal Domains. 77:1-77:17 - Tim Roughgarden, Joshua R. Wang:
The Complexity of the k-means Method. 78:1-78:14
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.