Skip to main content
SpringerLink
Log in
Book cover

Algorithms and Computation

15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings

  • Conference proceedings
  • © 2005

Overview

Editors:
  1. Rudolf Fleischer

    1. Department of Computer Science and Engineering, Fudan University, Shanghai, China

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Gerhard Trippen

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

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

Included in the following conference series:

Conference proceedings info: ISAAC 2004.

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

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.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

Table of contents (78 papers)

  1. Front Matter

    Download chapter PDF

  2. Puzzles, Art, and Magic with Algorithms

    • Erik D. Demaine
    Pages 1-1

  3. The ABCs of AVDs: Geometric Retrieval Made Simple

    • David M. Mount
    Pages 2-2

  4. Pareto Optimality in House Allocation Problems

    • David J. Abraham, Katarína Cechlárová, David F. Manlove, Kurt Mehlhorn
    Pages 3-15

  5. Property-Preserving Data Reconstruction

    • Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu
    Pages 16-27

  6. On the Monotone Circuit Complexity of Quadratic Boolean Functions

    • Kazuyuki Amano, Akira Maruoka
    Pages 28-40

  7. Generalized Function Matching

    • Amihood Amir, Igor Nor
    Pages 41-52

  8. Approximate Distance Oracles for Graphs with Dense Clusters

    • Mattias Andersson, Joachim Gudmundsson, Christos Levcopoulos
    Pages 53-64

  9. Multicriteria Global Minimum Cuts

    • Amitai Armon, Uri Zwick
    Pages 65-76

  10. Polyline Fitting of Planar Points Under Min-sum Criteria

    • Boris Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama
    Pages 77-88

  11. A Generalization of Magic Squares with Applications to Digital Halftoning

    • Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. Nandy, Shinji Sasahara, Takeaki Uno
    Pages 89-100

  12. Voronoi Diagrams with a Transportation Network on the Euclidean Plane

    • Sang Won Bae, Kyung-Yong Chwa
    Pages 101-112

  13. Structural Alignment of Two RNA Sequences with Lagrangian Relaxation

    • Markus Bauer, Gunnar W. Klau
    Pages 113-123

  14. Poly-APX- and PTAS-Completeness in Standard and Differential Approximation

    • Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos
    Pages 124-136

  15. Efficient Algorithms for k Maximum Sums

    • Fredrik Bengtsson, Jingsen Chen
    Pages 137-148

  16. Equipartitions of Measures by 2-Fans

    • Sergey Bereg
    Pages 149-158

  17. Augmenting the Edge-Connectivity of a Spider Tree

    • Davide Bilò, Guido Proietti
    Pages 159-171

  18. On Nash Equilibria for Multicast Transmissions in Ad-Hoc Wireless Networks

    • Vittorio Bilò, Michele Flammini, Giovanna Melideo, Luca Moscardelli
    Pages 172-183

  19. Structural Similarity in Graphs

    • Ulrik Brandes, Jürgen Lerner
    Pages 184-195

  20. Flexibility of Steiner Trees in Uniform Orientation Metrics

    • Marcus Brazil, Pawel Winter, Martin Zachariasen
    Pages 196-208
Back to top

Other volumes

  1. Algorithms and Computation

Keywords

About this book

This volume contains the proceedings of the 15th Annual International Sym- sium on Algorithms and Computation (ISAAC 2004), held in Hong Kong, 20–22 December, 2004. In the past, it has been held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), Chennai (1999), Taipei (2000), Christchurch (2001), Vancouver (2002), and Kyoto (2003). ISAAC is an annual international symposium that covers a wide range of topics,namelyalgorithmsandcomputation.Themainpurposeofthesymposium is to provide a forum for researchers working in the active research community of algorithms and the theory of computation to present and exchange new ideas. In response to our call for papers we received 226 submissions. The task of selectingthepapersinthisvolumewasdonebyourprogramcommitteeandother referees. After a thorough review process the committee selected 76 papers, the decisions being based on originality and relevance to the ?eld of algorithms and computation. We hope all accepted papers will eventually appear in scienti?c journals in a more polished form. Two special issues, one of Algorithmica and one of the International Journal of Computational Geometry and Applications, with selected papers from ISAAC 2004 are in preparation. Thebeststudentpaperawardwillbegivenfor“Geometricoptimizationpr- lems over sliding windows” by Bashir S. Sadjad and Timothy M. Chan from the University of Waterloo. Two eminent invited speakers, Prof. Erik D. Demaine, MIT, and Prof. David M. Mount, University of Maryland, also contributed to this volume.

Editors and Affiliations

  • Department of Computer Science and Engineering, Fudan University, Shanghai, China

    Rudolf Fleischer

  • Department of Computer Science, The Hong Kong University of Science and Technology, Hong Kong

    Gerhard Trippen

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation