Accepted Papers

3 Luc Devroye and Xing Shi Cai. A Probabilistic Analysis of Kademlia Networks
7 Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz and Birgit Vogtenhuber. Geodesic-Preserving Polygon Simplification
11 Leo Speidel and Konstantinos Panagiotou. Asynchronous Rumor Spreading on Random Graphs
12 Jinhee Chun, Ricardo Gonzalo and Takeshi Tokuyama. Space-efficient and data-sensitive polygon reconstruction algorithms from visibility angle information
15 Marek Karpinski, Michael Lampis and Richard Schmied. New Inapproximability Bounds for TSP
16 Bodo Manthey and Rianne Veenstra. Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise
17 Min Chih Lin, Michel J. Mizrahi and Jayme L. Szwarcfiter. An O(1.1939n) time algorithm for minimum weighted dominating induced matching
18 Gonzalo Navarro and Sharma V. Thankachan. Top-k Document Retrieval in Compact Space and Near-Optimal Time
20 Kyle Klein and Subhash Suri. Pursuit Evasion on Polyhedral Surfaces
26 Otfried Cheong, Sariel Har-Peled, Heuna Kim and Hyo-Sil Kim. On the Number of Edges of Fan-Crossing Free Graphs
41 Søren Kristoffer Stiil Frederiksen and Peter Bro Miltersen. Approximating the value of a concurrent reachability game in the polynomial time hierarchy
43 Chenglin Fan, Jun Luo and Binhai Zhu. Tight Approximation Bounds for Connectivity with a Color-Spanning Set
45 Patrizio Angelini, William Evans, Fabrizio Frati and Joachim Gudmundsson. SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs
48 Sergey Bereg, Seok-Hee Hong, Naoki Katoh, Sheung-Hung Poon and Shin-Ichi Tanigawa. On the Edge Crossing Properties of Euclidean Minimum Weight Laman Graphs
50 Akiyoshi Shioura, Kazuo Murota and Zaifu Yang. Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items
51 Mourad Baiou, Laurent Beaudou, Zhentao Li and Vincent Limouzy. Hardness and algorithms for variants of line graphs of directed graphs
54 Mingyu Xiao and Hiroshi Nagamochi. Exact Algorithms for Maximum Independent Set
55 Arnaud Mary, Mamadou Moustapha Kanté, Nourine Lhouari, Vincent Limouzy and Uno Takeaki. On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
58 Aparna Das, Krzysztof Fleszar, Stephen Kobourov, Joachim Spoerhase, Sankar Veeramoni and Alexander Wolff. Approximating the Generalized Minimum Manhattan Network Problem
59 Franz Aurenhammer and Gernot Walzl. Structure and computation of straight skeletons in 3-space
60 Amihood Amir and Benny Porat. Pattern Matching with non Overlapping Reversals - Approximation and On-line Algorithms
61 Xiangzhong Xiang. New Results on the Online Pricing Problem
62 Pegah Kamousi and Subhash Suri. Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
64 Wolfgang Mulzer and Yannik Stein. Algorithms for Tolerated Tverberg Partitions
70 Andreas Gemsa, Benjamin Niedermann and Martin Nöllenburg. Trajectory-Based Dynamic Map Labeling
71 Marc Lelarge and Hang Zhou. Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs
72 Cecilia Bohler and Rolf Klein. Abstract Voronoi Diagrams with Disconnected Regions
74 Patrizio Angelini, Thomas Bläsius and Ignaz Rutter. Testing Mutual Duality of Planar Graphs
80 Robert Bredereck, Sepp Hartung, André Nichterlein and Gerhard Woeginger. The complexity of finding a large subgraph under anonymity constraints
81 Jiehua Chen, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge, Ondrej Suchy and Mathias Weller. Effective and Efficient Data Reduction for the Minimum Topic-Connected Overlay Problem
82 Qi Cheng, Jincheng Zhuang and Jiyou Li. On Determing Deep Holes of Generalized Reed-Solomon Codes
86 Yota Otachi and Pascal Schweitzer. Isomorphism on subgraph-closed graph classes: a complexity dichotomy and intermediate graph classes
87 Matthew Johnson, Daniel Paulusma and Erik Jan van Leeuwen. Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs
89 Timothy Chan, Ian Munro and Venkatesh Raman. Faster, space efficient selection algorithms in read-only memory for integers
98 Youming Qiao, Xiaoming Sun and Nengkun Yu. Determinantal complexities and field extensions
101 Yasushi Kawase, Xin Han and Kazuhisa Makino. Unit Cost Buyback Problem
103 Pan Peng and Angsheng Li. Detecting and Characterizing Small Dense Bipartite-like Subgraphs by the Bipartiteness Ratio Measure
106 Djamal Belazzougui, Adeline Pierrot, Mathieu Raffinot and Stéphane Vialette. Single and multiple consecutive permutation motif search
109 Martin Farach-Colton and Meng-Tsung Tsai. Exact Sublinear Binomial Sampling
110 Dominik Scheder. Trivial, Tractable, Hard. A Not So Sudden Complexity Jump in Neighborhood Restricted CNF Formulas
111 Haitao Wang. Minmax Regret 1-Facility Location on Uncertain Path Networks
114 Kevin Buchin and Dirk H.P. Gerrits. Dynamic point labeling is strongly PSPACE-complete
117 Sharathkumar R and Michael Kerber. Approximate \v{C}ech complexes in low and high dimensions
118 Konstantinos Panagiotou, Ali Pourmiri and Thomas Sauerwald. Faster Rumor Spreading with Multiple Calls
120 Dominik Scheder. Unsatisfiable CNF Formulas Contain Many Conflicts
125 Lars Arge and Mikkel Thorup. RAM-Efficient External Memory Sorting
128 Robert Fraser, Meng He, Akitoshi Kawamura, Alejandro Lopez-Ortiz, J. Ian Munro and Patrick K. Nicholson. The Distance 4-Sector of Two Points is Unique
129 Pawel Gawrychowski and Damian Straszak. Beating O(nm) in approximate LZW-compressed pattern matching
130 Ferran Hurtado, Maarten Löffler, Ines Matos, Vera Sacristan, Maria Saumell, Rodrigo Silveira and Frank Staals. Terrain visibility with multiple viewpoints
131 Moshe Lewenstein, Ian Munro and Venkatesh Raman. Succinct data structures for representing equivalence classes
132 Friedrich Slivovsky and Stefan Szeider. Model Counting for Formulas of Bounded Boolean-Width
133 Michael Etscheid. Performance Guarantees for Scheduling Algorithms under Perturbed Machine Speeds
139 Greg Plaxton. Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs
142 Jing Chen, Xin Han and Kazuo Iwama. The Train Delivery Problem Revisited
144 Sharma V. Thankachan, J. Ian Munro, Venkatesh Raman and Moshe Lewenstein. Less Space: Indexing for Queries with Wildcards
150 Takashi Horiyama and Wataru Shoji. The Number of Different Unfoldings of Polyhedra
152 René Van Bevern, Michael R. Fellows, Serge Gaspers and Frances A. Rosamond. Myhill-Nerode Methods for Hypergraphs
153 Martin Balko, Pavel Klavík and Yota Otachi. Bounded Representations of Interval and Proper Interval Graphs
154 Jun Kawahara, Koji M. Kobayashi and Shuichi Miyazaki. Better Bounds for Online $k$-Frame Throughput Maximization in Network Switches
160 Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson and Luke Mathieson. Augmenting Graphs to Minimize the Diameter
163 Samuel Walker and Yakov Zinder. The Solvable Cases of a Scheduling Algorithm
164 Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang and Kun-Mao Chao. Computing Plurality Points and Condorcet Points in Euclidean Space
168 Eylon Yogev and Moni Naor. Sliding Bloom Filters
171 Payam Khanteimouri, Ali Mohades, Mohammad Ali Abam and Mohammad Reza Kazemi. Computing the Smallest Color-Spanning Axes-Parallel Square
173 Aleck Johnsen, Ming-Yang Kao and Shinnosuke Seki. Computing Minimum Tile Sets to Self-Assemble Colors Patterns
174 Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas and Eva-Marta Lundell. Detecting and Counting Small Pattern Graphs
178 Tomáš Gavenčiak, Vít Jelínek, Pavel Klavík and Jan Kratochvíl. Cops and Robbers on Intersection Graphs