Accepted Papers

011. N. Bourgeois, F. Della Croce, B. Escoffier, and V. Th. Paschos, Exact algorithms for dominating clique problems.

013. Jens M. Schmidt, Interval Stabbing Problems in Small Integer Ranges.

019. Kazumasa Okumoto, Takuro Fukunaga, and Hiroshi Nagamochi, Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems.

020. Takuro Fukunaga, Graph Orientations with Set Connectivity Requirements.

022. Sanjiv Kapoor and Xiang-Yang Li, Geodesic Spanners on Polyhedral Surfaces.

023. Ping Xu and XiangYang Li, SOFA: Strategyproof Online Frequency Allocation for
Multihop Wireless Networks.

029. George Karakostas, General pseudo-random generators from weaker models of computation

036. Daniel Andersson and Peter Bro Miltersen, The Complexity of Solving Stochastic Games on Graphs.

039. Chuzo Iwamoto, Kento Sasaki, Kenji Nishio, and Kenichi Morita, Computational Complexity of Cast Puzzles.

040. Riko Jacob, Stephan Ritscher, Christian Scheideler, and Stefan Schmid, A Self Stabilizing and Local Delaunay Graph Construction.

043. Xiao Zhou and Takao Nishizeki, Convex Drawings of Internally Triconnected Plane Graphs on O(n2) Grids.

044. Francis Y.L. Chin, Hing-Fung Ting, and Yong Zhang, 1-Space Bounded Algorithms for 2-Dimensional Bin Packing.

050. Raphael Eidenbenz and Roger Wattenhofer, Good Programming in Transactional Memory Game Theory Meets Multicore Architecture.

051. Bodo Manthey and Heiko Röglin, Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences.

053. Wing-Kai Hon, Tak-Wah Lam, Rahul Shah, Siu-Lung Tam, and Jeffrey Scott Vitter, Succinct Index for Dynamic Dictionary Matching.

055. Takeshi Tokuyama, Matias Korman, Ryosei Kasai, and Jinhee Chun, Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes.

056. Adrian Dumitrescu and Csaba D. Tóth, New Bounds on the Average Distance from the
Fermat-Weber Center of a Planar Convex Body.

057. Gerth Stølting Brodal, Alexis C. Kaporis, Spyros Sioutas, Konstantinos Tsakalidis, and Kostas Tsichlas, Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time.

058. Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, and Ryuhei Uehara, Random Generation and Enumeration of Bipartite Permutation Graphs.

059. Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve, and Alejandro López-Ortiz, Online Sorted Range Reporting.

061. Yakov Nekrich, Data Structures for Approximate Orthogonal Range Counting.

063. Shiteng Chen, Zhiyi Huang, and Sampath Kannan, Reconstructing Numbers from Pairwise Function Values.

064. Li Chen and Bin Fu, Linear and Sublinear Time Algorithms for Basis of Abelian Groups.

067. Hagai Cohen and Ely Porat, Range Non-Overlapping Indexing.

072. Kristoffer Arnsfelt Hansen, Oded Lachish, and Peter Bro Miltersen, Hilbert’s Thirteenth Problem and Circuit Complexity.

074. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královic, Richard Královic, and Tobias Mömke, On the Advice Complexity of Online Problems.

077. Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Stéphan Thomassé, A Linear Vertex Kernel for Maximum Internal Spanning Tree.

078. Danny Z. Chen and Haitao Wang, Approximating Points by a Piecewise Linear Function: I.

079. Danny Z. Chen and Haitao Wang, Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers.

081. Khaled Elbassioni and Hans Raj Tiwary, Complexity of Approximating the Vertex
Centroid of a Polyhedron.

084. Tomoki Imada, Shunsuke Ota, Hiroshi Nagamochi, and Tatsuya Akutsu, Enumerating Stereoisomers of Tree Structured Molecules Using Dynamic Programming.

086. Dae Young Seo, D. T. Lee, and Tien-Ching Lin, Geometric Minimum Diameter Minimum Cost Spanning Tree Problem.

087. Tien-Ching Lin and D. T. Lee, Optimal Randomized Algorithm for the Density Selection Problem.

088. Sang Won Bae and Yoshio Okamoto, Querying Two Boundary Points for Shortest Paths in a Polygonal Domain.

091. Jinhui Xu, Lei Xu, and Evanthia Papadopoulou, Computing the Map of Geometric Minimal Cuts.

092. Yusuke Kobayashi and Christian Sommer, On Shortest Disjoint Paths in Planar Graphs.

094. Telikepalli Kavitha and Meghana Nasre, Popular Matchings with Variable Job Capacities.

097. Shengyu Zhang, On the Tightness of the Buhrman-Cleve-Wigderson Simulation.

098. Xin Han and Kazuhisa Makino, Online Knapsack Problems with Limited Cuts.

101. Johannes Schneider and Roger Wattenhofer, Bounds on Contention Management Algorithms.

104. Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Stefan Langerman, and Ryuhei Uehara, Algorithmic Folding Complexity.

105. Petr A. Golovach, Marcin Kaminski, Daniël Paulusma, and Dimitrios M. Thilikos, Induced Packing of Odd Cycles in a Planar Graph.

108. Tai-Hsin Hsu and Hsueh-I Lu, An Optimal Labeling for Node Connectivity.

109. Rudolf Fleischer and Yihui Wang, On the Camera Placement Problem.

111. Tsung-Hao Liu and Hsueh-I Lu, Minimum Cycle Bases of Weighted Outerplanar Graphs.

113. Jiong Guo, Christian Komusiewicz, Iyad A. Kanj, and Johannes Uhlmann, Editing Graphs into Disjoint Unions of Dense Clusters.

114. R. Chandrasekaran and K. Subramani, A Combinatorial Algorithm for Horn Programs.

117. Petr Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister, and Saket Saurabh, Bandwidth on AT-free graphs.

118. Therese Biedl, Stephane Durocher, and Jack Snoeyink, Reconstructing Polygons from Scanner Data.

121. Shuai Cheng Li and Yen Kaow Ng, On Protein Structure Alignment under Distance Constraint.

124. Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel, and Maxim Sviridenko, A Structural Lemma in 2-Dimensional Packing, and its Implications on Approximability.

125. Naoki Katoh and Shin-ichi Tanigawa, On the Infinitesimal Rigidity of Bar-and-slider Frameworks.

126. Paola Flocchini, Bernard Mans, and Nicola Santoro, Exploration of Periodically Varying Graphs.

127. Jiong Guo, Rolf Niedermeier, and Ondrej Suchy, Parameterized Complexity of Arc-Weighted Directed Steiner Problems.

130. Telikepalli Kavitha1 and Julián Mestre, Max-coloring paths: Tight bounds and extensions.

131. Sang Won Bae, Sunghee Choi, Chunseok Lee, and Shin-ichi Tanigawa, Exact Algorithms for the Bottleneck Steiner Tree Problem.

134. Gerth Stølting Brodal and Allan Grønlund Jørgensen, Data Structures for Range Median Queries.

135. Daniel Bruce, Chính T. Hoàng, and Joe Sawada, A Certifying Algorithm for 3-Colorability of P5-Free Graphs

136. Gerth Stølting Brodal, Allan Grønlund Jørgensen, Gabriel Moruz, and Thomas Mølhave, Counting in the Presence of Memory Faults.

138. Annamaria Kovacs, Ulrich Meyer, Gabriel Moruz, and Andrei Negoescu, Online Paging for Flash Memory Devices.

139. Christian Knauer, Maarten Löffler, Marc Scherfenberg, and Thomas Wolle, The Directed Hausdor Distance between 2 Imprecise Point Sets.

140. Takehiro Ito, Marcin Kaminski, Daniël Paulusma, and Dimitrios Thilikos, Parameterizing Cut Sets in a Graph by the Number of Their Components.

141. Gunnar Carlsson, Gurjeet Singh, and Afra Zomorodian, Computing Multidimensional Persistence.

146. Robert Franke, Ignaz Rutter, and Dorothea Wagner, Computing Large Matchings in Planar Graphs with Fixed Minimum Degree.

148. Danny Z. Chen and Haitao Wang, Locating an Obnoxious Line among Planar Objects.

149. Decheng Dai and Rong Ge, New Results on Simple Stochastic Games.

150. Siddhartha Sen and Robert E. Tarjan, Deletion Without Rebalancing in Multiway Search Trees.

153. Weiwei Wu, Minming Li, and Enhong Chen, Min-Energy Scheduling for Aligned Jobs in
Accelerate Model.

155. Yoshitaka Nakao and Hiroshi Nagamochi, Worst Case Analysis for Pickup and Delivery
Problems with Consecutive Pickups and Deliveries.

157. Tamara Mchedlidze and Antonios Symvonis, Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs.

162. Cristina Bazgan, Basile Couëtoux, and Zsolt Tuza, Covering a Graph with a Constrained Forest.

166. Minghui Jiang, Inapproximability of Maximal Strip Recovery.

167. Qiang-Sheng Hua , Dongxiao Yu, Francis C.M. Lau, and Yuexuan Wang, Faster Exact Algorithms for Set Multicover and Multiset Multicover Problems.

171. Paul Bonsma and Felix Breuer, Finding Fullerene Patches in Polynomial Time.

173. Lars Arge and Morten Revsbaek, I/O-Efficient Contour Tree Simplification.

178. Yam Ki Cheung and Ovidiu Daescu, Fréchet Distance Problems in Weighted Regions.

179. Michael T. Goodrich and Darren Strash, Succinct Greedy Geometric Routing in the Euclidean Plane.

183. Jonathan Kelner and Petar Maymounkov, Electric Routing and Concurrent Flow Cutting.

184. Marwan Al-Jubeh, Mashhood Ishaque, Kristóf Rédei, Diane L. Souvaine, and Csaba D. Tóth, Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs.

185. Imran A. Pirwani, Shifting Strategy for Geometric Graphs Without Geometry.

189. Minming Li, Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics.

190. Amotz Bar-Noy and Michael Lampis, Online Maximum Directed Cut.

193. Marek Karpinski, Andrzej Rucinski, and Edyta Szymanska, The Complexity of Perfect Matching Problems on Dense Hypergraphs.

199. Liang Xu and Zhou Xu, Approximation Algorithms for Min-max Path Cover Problems
with Service Handling Time.

201. Diego Arroyuelo, Francisco Claude, Reza Dorrigiv, Stephane Durocher, Meng He, Alejandro López-Ortiz, J. Ian Munro, Patrick K. Nicholson, Alejandro Salinger, and Matthew Skala, Untangled Monotonic Chains and Adaptive Range Search.

204. Sándor P. Fekete, Joseph S. B. Mitchell, and Christiane Schmidt, Minimum Covering with Travel Cost.

207. Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, and Ryuhei Uehara, Route-Enabling Graph Orientation Problems.

210. V. Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan, On Lower Bounds for Constant Width Arithmetic Circuits.

211. Ping-Hui Hsu, Kuan-Yu Chen, and Kun-Mao Chao, Finding All Approximate Gapped Palindromes.

213. Seok-Hee Hong and Hiroshi Nagamochi, Upward Star-shaped Polyhedral Graphs.

214. Craig Dillabaugh, Meng He, Anil Maheshwari, and Norbert Zeh, I/O and Space-Efficient Path Traversal in Planar Graphs.

215. Xi Chen and Shang-Hua Teng, Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria.

216. Jin Wook Kim, Siwon Choi, Joong Chae Na, and Jeong Seop Sim, Improved Algorithms for Finding Consistent Superstrings based on a New Graph Model.

218. Paul C. Bell and Igor Potapov, The Identity Correspondence Problem and its Applications.

219. Andrzej Czygrinow, Michal Hanckowiak, and Edyta Szymanska, Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs.

220. Scott Schneider and Michael Spertus, A Simple, Fast, and Compact Static Dictionary.

221. Minkyoung Cho, David M. Mount, and Eunhui Park, Maintaining Nets and Net Trees under Incremental Motion.

223. Francisco Claude, Reza Dorrigiv, Stephane Durocher, Robert Fraser, Alejandro López-Ortiz, and Alejandro Salinger, Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm.

225. Daisuke Yamaguchi, Shinji Imahori, Ryuhei Miyashiro, and Tomomi Matsui, An Improved Approximation Algorithm for the Traveling Tournament Problem.

226. Shihong Xu and Hong Shen, The Fault-Tolerant Facility Allocation Problem.

230. Linqing Tang, Conditional Hardness of Approximating Satisfiable Max 3CSP-q.

234. Shivali Agarwal, Ankur Narang, and Rudrapatna K. Shyamasundar, Distributed Scheduling of Parallel Hybrid Computations.

237. Tomoyuki Yamakami, The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata.

238. Pei-Chi Huang, Hsin-Wen Wei, Yen-Chiu Chen, Ming-Yang Kao, Wei-Kuan Shih, and Tsan-sheng Hsu, Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint.

239. Toshimasa Ishii and Kazuhisa Makino, Posi-modular Systems with Modulotone
Requirements under Permutation Constraints.

240. Minming Li, Peng-Jun Wan, and Frances Yao, Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks.

243. Naoyuki Kamiyama and Naoki Katoh, A Polynomial-Time Algorithm for the Universally
Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths.

247. Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Corentin Travers, Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement.

254. Deepanjan Kesh and Shashank K. Mehta, Generalized Reduction to Compute Toric Ideals.

256. Laurent Bulteau, Guillaume Fertin, and Irena Rusu, Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms.

258. Sylvain Guillemot, Jesper Jansson, and Wing-Kin Sung, Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets.

261. Sylvain Guillemot and Stéphane Vialette, Pattern Matching for 321-Avoiding Permutations.

266. Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate, and Chaitanya Swamy, Approximation Algorithms for the Fire Fighter Problem: Cuts over Time and Submodularity.

274. Qian-Ping Gu and Hisao Tamaki, Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n1+ε) Time.

278. Benjamin Doerr, Anna Huber, and Ariel Levavi, Strong Robustness of Randomized
Rumor Spreading Protocols.

279. Daniël Paulusma and Johan M.M. van Rooij, On Partitioning a Graph into Two Connected Subgraphs.

283. Ján Manuch, Ladislav Stacho, and Christine Stoll, Step-Assembly with a Constant Number of Tile Types.

284. Erik D. Demaine, Martin L. Demaine, Goran Konjevodz, and Robert J. Lang, Folding a Better Checkerboard.

287. Donald Stanley and Boting Yang, Lower Bounds on Fast Searching and Their Applications.

290. Anna Adamaszek, Artur Czumaj, and Andrzej Lingas, PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k.