| Description |
1 online resource |
| Series |
Lecture notes in computer science, 0302-9743 ; 7501 |
|
Advanced research in computing and software science |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 7501.
|
|
Lecture notes in computer science. Advanced research in computing and software science.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
On Big Data Algorithmics / Yossi Matias -- Open Problems in Throughput Scheduling / Jiří Sgall -- Preemptive Coordination Mechanisms for Unrelated Machines / Fidaa Abed and Chien-Chung Huang -- Hierarchical Hub Labelings for Shortest Paths / Ittai Abraham, Daniel Delling, Andrew V. Goldberg and Renato F. Werneck -- Bottleneck Non-crossing Matching in the Plane / A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz and Yohai Trabelsi -- Lower Bounds for Sorted Geometric Queries in the I/O Model / Peyman Afshani and Norbert Zeh -- Constructing Street Networks from GPS Trajectories / Mahmuda Ahmed and Carola Wenk -- I/O-efficient Hierarchical Diameter Approximation / Deepak Ajwani, Ulrich Meyer and David Veith -- On the Value of Job Migration in Online Makespan Minimization / Susanne Albers and Matthias Hellwig -- Simplifying Massive Contour Maps / Lars Arge, Lasse Deleuran, Thomas Mølhave, Morten Revsbæk and Jakob Truelsen -- Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash / Martin Aumüller, Martin Dietzfelbinger and Philipp Woelfel -- On Online Labeling with Polynomially Many Labels / Martin Babka, Jan Bulánek, Vladimír Čunát, Michal Koucký and Michael Saks -- A 5-Approximation for Capacitated Facility Location / Manisha Bansal, Naveen Garg and Neelima Gupta -- Weighted Geometric Set Multi-cover via Quasi-uniform Sampling / Nikhil Bansal and Kirk Pruhs -- A Bicriteria Approximation for the Reordering Buffer Problem / Siddharth Barman, Shuchi Chawla and Seeun Umboh -- Time-Dependent Route Planning with Generalized Objective Functions / Gernot Veit Batz and Peter Sanders -- New Lower and Upper Bounds for Representing Sequences / Djamal Belazzougui and Gonzalo Navarro -- Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection / Aleksandrs Belovs and Ben W. Reichardt -- The Stretch Factor of L₁- and L∞-Delaunay Triangulations / Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse and Ljubomir Perković -- Two Dimensional Range Minimum Queries and Fibonacci Lattices / Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman and Satti Srinivasa Rao -- Locally Correct Fréchet Matchings / Kevin Buchin, Maike Buchin, Wouter Meulemans and Bettina Speckmann -- The Clique Problem in Ray Intersection Graphs / Sergio Cabello, Jean Cardinal and Stefan Langerman -- Revenue Guarantees in Sponsored Search Auctions / Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos and Maria Kyropoulou -- Optimizing Social Welfare for Network Bargaining Games in the Face of Unstability, Greed and Spite / T. -H. Hubert Chan, Fei Chen and Li Ning -- Optimal Lower Bound for Differentially Private Multi-party Aggregation / T-H. Hubert Chan, Elaine Shi and Dawn Song -- A Model for Minimizing Active Processor Time / Jessica Chang, Harold N. Gabow and Samir Khuller -- Polynomial-Time Algorithms for Energy Games with Special Weight Structures / Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai -- Data Structures on Event Graphs / Bernard Chazelle and Wolfgang Mulzer -- Improved Distance Oracles and Spanners for Vertex-Labeled Graphs / Shiri Chechik -- The Quantum Query Complexity of Read-Many Formulas / Andrew M. Childs, Shelby Kimmel and Robin Kothari -- A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees / Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk and Piotr Sankowski -- Steiner Forest Orientation Problems / Marek Cygan, Guy Kortsarz and Zeev Nutov -- A Dual-Fitting \frac3223-Approximation Algorithm for Some Minimum-Cost Graph Problems / James M. Davis and David P. Williamson -- Kinetic Compressed Quadtrees in the Black-Box Model with Applications to Collision Detection for Low-Density Scenes / Mark de Berg, Marcel Roeloffzen and Bettina Speckmann -- Finding Social Optima in Congestion Games with Positive Externalities / Bart de Keijzer and Guido Schäfer -- Better Bounds for Graph Bisection / Daniel Delling and Renato F. Werneck -- On the Complexity of Metric Dimension / Josep Díaz, Olli Pottonen, Maria Serna and Erik Jan van Leeuwen -- Embedding Paths into Trees: VM Placement to Minimize Congestion / Debojyoti Dutta, Michael Kapralov, Ian Post and Rajendra Shinde -- Faster Geometric Algorithms via Dynamic Determinant Computation / Vissarion Fisikopoulos and Luis Peñaranda -- Lines through Segments in 3D Space / Efi Fogel, Michael Hemmer, Asaf Porat and Dan Halperin -- A Polynomial Kernel for Proper Interval Vertex Deletion / Fedor V. Fomin, Saket Saurabh and Yngve Villanger -- Knowledge, Level of Symmetry, and Time of Leader Election / Emanuele G. Fusco and Andrzej Pelc -- An Experimental Study of Dynamic Dominators / Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura and Federico Santaroni -- Optimizing over the Growing Spectrahedron / Joachim Giesen, Martin Jaggi and Sören Laue -- Induced Disjoint Paths in Claw-Free Graphs / Petr A. Golovach, Daniël Paulusma and Erik Jan van Leeuwen -- On Min-Power Steiner Tree / Fabrizio Grandoni -- Maximum Multicommodity Flows over Time without Intermediate Storage / Martin Groß and Martin Skutella -- Approximating Earliest Arrival Flows in Arbitrary Networks / Martin Groß, Jan-Philipp W. Kappmeier, Daniel R. Schmidt and Melanie Schmidt -- Resource Buying Games / Tobias Harks and Britta Peis -- Succinct Data Structures for Path Queries / Meng He, J. Ian Munro and Gelin Zhou -- Approximation of Minimum Cost Homomorphisms / Pavol Hell, Monaldo Mastrolilli, Mayssam Mohammadi Nevisi and Arash Rafiey -- Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph-Freeness / Frank Hellweg and Christian Sohler -- Improved Implementation of Point Location in General Two-Dimensional Subdivisions / Michael Hemmer, Michal Kleinbort and Dan Halperin -- Parameterized Complexity of Induced H-Matching on Claw-Free Graphs / Danny Hermelin, Matthias Mnich and Erik Jan van Leeuwen -- Solving Simple Stochastic Games with Few Coin Toss Positions / Rasmus Ibsen-Jensen and Peter Bro Miltersen -- Efficient Communication Protocols for Deciding Edit Distance / Hossein Jowhari -- Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates / Thomas Kesselheim -- Extending Partial Representations of Function Graphs and Permutation Graphs / Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk and Bartosz Walczak -- A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization / Yasuaki Kobayashi and Hisao Tamaki -- Minimum Average Distance Triangulations / László Kozma -- Colouring AT-Free Graphs / Dieter Kratsch and Haiko Müller -- Routing Regardless of Network Stability / Bundit Laekhanukit, Adrian Vetta and Gordon Wilfong -- The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes / Jean-Daniel Boissonnat and Clément Maria -- Succinct Posets / J. Ian Munro and Patrick K. Nicholson -- Polynomial-Time Approximation Schemes for Shortest Path with Alternatives / Tim Nonner -- On Computing Straight Skeletons by Means of Kinetic Triangulations / Peter Palfrader, Martin Held and Stefan Huber -- A Self-adjusting Data Structure for Multidimensional Point Sets / Eunhui Park and David M. Mount -- TSP Tours in Cubic Graphs: Beyond 4/3 / José R. Correa, Omar Larré and José A. Soto -- FPT Algorithms for Domination in Biclique-Free Graphs / Jan Arne Telle and Yngve Villanger -- Maximum Flow Networks for Stability Analysis of LEGO® Structures / Martin Waßmann and Karsten Weicker -- Average Case Analysis of Java 7's Dual Pivot Quicksort / Sebastian Wild and Markus E. Nebel |
| Summary |
This book constitutes the refereed proceedings of the 20th Annual European Symposium on Algorithms, ESA 2012, held in Ljubljana, Slovenia, in September 2012 in the context of the combined conference ALGO 2012. The 69 revised full papers presented were carefully reviewed and selected from 285 initial submissions: 56 out of 231 in track design and analysis and 13 out of 54 in track engineering and applications. The papers are organized in topical sections such as algorithm engineering; algorithmic aspects of networks; algorithmic game theory; approximation algorithms; computational biology; computational finance; computational geometry; combinatorial optimization; data compression; data structures; databases and information retrieval; distributed and parallel computing; graph algorithms; hierarchical memories; heuristics and meta-heuristics; mathematical programming; mobile computing; on-line algorithms; parameterized complexity; pattern matching, quantum computing; randomized algorithms; scheduling and resource allocation problems; streaming algorithms |
| Analysis |
Computer science |
|
Computer Communication Networks |
|
Data structures (Computer science) |
|
Computer software |
|
Electronic data processing |
|
Computational complexity |
|
Computer graphics |
|
Algorithm Analysis and Problem Complexity |
|
Discrete Mathematics in Computer Science |
|
Numeric Computing |
|
computerwetenschappen |
|
computer sciences |
|
numerieke methoden |
|
numerical methods |
|
computertechnieken |
|
computer techniques |
|
wiskunde |
|
mathematics |
|
algoritmen |
|
algorithms |
|
computeranalyse |
|
computer analysis |
|
gegevensstructuren |
|
data structures |
|
computergrafie |
|
computernetwerken |
|
computer networks |
|
Information and Communication Technology (General) |
|
Informatie- en communicatietechnologie (algemeen) |
| Notes |
International conference proceedings |
| Bibliography |
Includes bibliographical references and author index |
| Subject |
Computer algorithms -- Congresses
|
|
Computer science -- Mathematics -- Congresses
|
|
Data structures (Computer science) -- Congresses
|
|
Informatique.
|
|
Computer algorithms
|
|
Computer science -- Mathematics
|
|
Data structures (Computer science)
|
| Genre/Form |
Conference papers and proceedings
|
|
Software.
|
| Form |
Electronic book
|
| Author |
Epstein, Leah
|
|
Ferragina, Paolo, 1969-
|
| ISBN |
9783642330902 |
|
3642330908 |
|
