Algorithms and Computation

1. Front Matter

   PDF

2. Invited Talk Paper

   1. Market Approach to Social Ads: The MyLikes Example and Related Problems

      • Darja Krushevskaja, S. Muthukrishnan

      Pages 1-10

3. Session 1A: Computational Geometry I

   1. Geodesic-Preserving Polygon Simplification

      • Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Birgit Vogtenhuber

      Pages 11-21

   2. Space-Efficient and Data-Sensitive Polygon Reconstruction Algorithms from Visibility Angle Information

      • Jinhee Chun, Ricardo Garcia de Gonzalo, Takeshi Tokuyama

      Pages 22-32

   3. On the Edge Crossing Properties of Euclidean Minimum Weight Laman Graphs

      • Sergey Bereg, Seok-Hee Hong, Naoki Katoh, Sheung-Hung Poon, Shin-ichi Tanigawa

      Pages 33-43

   4. Structure and Computation of Straight Skeletons in 3-Space

      • Franz Aurenhammer, Gernot Walzl

      Pages 44-54

4. Session 1B: Pattern Matching

   1. Pattern Matching with Non Overlapping Reversals - Approximation and On-line Algorithms

      • Amihood Amir, Benny Porat

      Pages 55-65

   2. Single and Multiple Consecutive Permutation Motif Search

      • Djamal Belazzougui, Adeline Pierrot, Mathieu Raffinot, Stéphane Vialette

      Pages 66-77

   3. Beating \(\mathcal{O}(nm)\) in Approximate LZW-Compressed Pattern Matching

      • Paweł Gawrychowski, Damian Straszak

      Pages 78-88

   4. Less Space: Indexing for Queries with Wildcards

      • Moshe Lewenstein, J. Ian Munro, Venkatesh Raman, Sharma V. Thankachan

      Pages 89-99

5. Session 2A: Computational Complexity I

   1. On Determining Deep Holes of Generalized Reed-Solomon Codes

      • Qi Cheng, Jiyou Li, Jincheng Zhuang

      Pages 100-110

   2. Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes

      • Yota Otachi, Pascal Schweitzer

      Pages 111-118

   3. Determinantal Complexities and Field Extensions

      • Youming Qiao, Xiaoming Sun, Nengkun Yu

      Pages 119-129

6. Session 2B: Internet and Social Network Algorithms I

   1. Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs

      • Matthew Johnson, Daniël Paulusma, Erik Jan van Leeuwen

      Pages 130-140

   2. Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs

      • Marc Lelarge, Hang Zhou

      Pages 141-151

   3. The Complexity of Finding a Large Subgraph under Anonymity Constraints

      • Robert Bredereck, Sepp Hartung, André Nichterlein, Gerhard J. Woeginger

      Pages 152-162

7. Session 3A: Graph Theory and Algorithms I

   1. On the Number of Edges of Fan-Crossing Free Graphs

      • Otfried Cheong, Sariel Har-Peled, Heuna Kim, Hyo-Sil Kim

      Pages 163-173

   2. Cops and Robbers on Intersection Graphs

      • Tomás Gavenčiak, Vít Jelínek, Pavel Klavík, Jan Kratochvíl

      Pages 174-184

   3. SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs

      • Patrizio Angelini, William Evans, Fabrizio Frati, Joachim Gudmundsson

      Pages 185-195

   4. Hardness and Algorithms for Variants of Line Graphs of Directed Graphs

      • Mourad Baïou, Laurent Beaudou, Zhentao Li, Vincent Limouzy

      Pages 196-206

This book constitutes the refereed proceedings of the 24th International Symposium on Algorithms and Computation, ISAAC 2013, held in Hong Kong, China in December 2013. The 67 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 177 submissions for inclusion in the book. The focus of the volume in on the following topics: computation geometry, pattern matching, computational complexity, internet and social network algorithms, graph theory and algorithms, scheduling algorithms, fixed-parameter tractable algorithms, algorithms and data structures, algorithmic game theory, approximation algorithms and network algorithms.

• approximation
• auctions
• polynomial time
• rumor spreading
• subgraphs
• algorithm analysis and problem complexity
• data structures

• Department of Computer Science and Engineering, Chinese University of Hong Kong, Hong Kong, China

  Leizhen Cai

• Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Hong Kong, China

  Siu-Wing Cheng

• Department of Computer Science, University of Hong Kong, Hong Kong, China

  Tak-Wah Lam

Policies and ethics