Algorithm Theory -- SWAT 2012

1. Front Matter

   PDF

2. α-Visibility

   • Mohammad Ghodsi, Anil Maheshwari, Mostafa Nouri, Jörg-Rüdiger Sack, Hamid Zarrabi-Zadeh

   Pages 1-12

3. Partial Matching between Surfaces Using Fréchet Distance

   • Jessica Sherette, Carola Wenk

   Pages 13-23

4. A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares

   • Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno et al.

   Pages 24-35

5. Watchman Routes for Lines and Segments

   • Adrian Dumitrescu, Joseph S. B. Mitchell, Paweł Żyliński

   Pages 36-47

6. Kinetic Pie Delaunay Graph and Its Applications

   • Mohammad Ali Abam, Zahed Rahmati, Alireza Zarei

   Pages 48-58

7. Higher Order City Voronoi Diagrams

   • Andreas Gemsa, D. T. Lee, Chih-Hung Liu, Dorothea Wagner

   Pages 59-70

8. On Minimum Sum of Radii and Diameters Clustering

   • Babak Behsaz, Mohammad R. Salavatipour

   Pages 71-82

9. A Simple Framework for the Generalized Nearest Neighbor Problem

   • Tomas Hruz, Marcel Schöngens

   Pages 83-94

10. Deterministic Parameterized Connected Vertex Cover

    • Marek Cygan

    Pages 95-106

11. Faster Parameterized Algorithms for Deletion to Split Graphs

    • Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai et al.

    Pages 107-118

12. A Single-Exponential FPT Algorithm for the K ₄-Minor Cover Problem

    • Eun Jung Kim, Christophe Paul, Geevarghese Philip

    Pages 119-130

13. An O(n ³ loglogn/log² n) Time Algorithm for All Pairs Shortest Paths

    • Yijie Han, Tadao Takaoka

    Pages 131-141

14. Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths

    • Aistis Atminas, Vadim V. Lozin, Igor Razgon

    Pages 142-152

15. Induced Disjoint Paths in AT-Free Graphs

    • Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen

    Pages 153-164

16. Effective Computation of Immersion Obstructions for Unions of Graph Classes

    • Archontia C. Giannopoulou, Iosif Salem, Dimitris Zoros

    Pages 165-176

17. Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain

    • Danny Z. Chen, Yan Gu, Jian Li, Haitao Wang

    Pages 177-188

18. Annotating Simplices with a Homology Basis and Its Applications

    • Oleksiy Busaryev, Sergio Cabello, Chao Chen, Tamal K. Dey, Yusu Wang

    Pages 189-200

19. Do Directional Antennas Facilitate in Reducing Interferences?

    • Rom Aschner, Matthew J. Katz, Gila Morgenstern

    Pages 201-212

20. Minimum Convex Partitions and Maximum Empty Polytopes

    • Adrian Dumitrescu, Sariel Har-Peled, Csaba D. Tóth

    Pages 213-224

This book constitutes the refereed proceedings of the 13th International Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012, held in Helsinki, Finland, in July 2012, co-located with the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012. The 34 papers were carefully reviewed and selected from a total of 127 submissions. The papers present original research and cover a wide range of topics in the field of design and analysis of algorithms and data structures.

• approximation algorithms
• complexity
• graph algorithms
• pattern matching
• string algorithms
• algorithm analysis and problem complexity
• data structures

• Institute of Informatics, University of Bergen, Bergen, Norway

  Fedor V. Fomin

• Department of Information and Computer Science, Aalto University, Aalto, Finland

  Petteri Kaski

Policies and ethics