[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Algorithms and Computation

24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings

  • Conference proceedings
  • © 2013

Overview

Editors:
  1. Leizhen Cai

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Siu-Wing Cheng

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Tak-Wah Lam

    1. Department of Computer Science, University of Hong Kong, Hong Kong, China

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Up-to-date results Proceedings of the 24th International Symposium on Algorithms and Computation, ISAAC 2013

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 8283)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: ISAAC 2013.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

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.

Similar content being viewed by others

Keywords

Table of contents (68 papers)

  1. Front Matter

    Download chapter 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
Back to top

Other volumes

  1. Algorithms and Computation

Editors and Affiliations

  • 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

Bibliographic Information

Publish with us

Policies and ethics

Back to top