+612 9045 4394
Algorithms and Computation : 14th International Symposium, Isaac 2003, Kyoto, Japan, December 15-17, 2003, Proceedings - Toshihide Ibaraki

Algorithms and Computation

14th International Symposium, Isaac 2003, Kyoto, Japan, December 15-17, 2003, Proceedings

By: Toshihide Ibaraki (Editor), Naoki Katoh (Editor), Hirotaka Ono (Editor)

Paperback Published: 3rd December 2003
ISBN: 9783540206958
Number Of Pages: 748

Share This Book:


or 4 easy payments of $51.04 with Learn more
Ships in 5 to 9 business days

This volume contains the proceedings of the 14th Annual International S- posium on Algorithms and Computation (ISAAC 2003), held in Kyoto, Japan, 15-17 December 2003. In the past, it was 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), and Vancouver (2002). ISAACisanannualinternationalsymposiumthatcoverstheverywiderange of topics in algorithms and computation. The main purpose of the symposium is to provide a forum for researchers working in algorithms and the theory of computation where they can exchange ideas in this active research community. In response to our call for papers, we received unexpectedly many subm- sions, 207 papers. The task of selecting the papers in this volume was done by our program committee and referees. After a thorough review process, the committee selected 73 papers. The selection was done on the basis of originality and relevance to the ?eld of algorithms and computation. We hope all accepted papers will eventally appear in scienti?c journals in more polished forms. The best paper award was given for "On the Geometric Dilation of Finite Point Sets" to Annette Ebbers-Baumann, Ansgar Grune ยจ and Rolf Klein. Two eminent invited speakers, Prof. Andrew Chi-Chih Yao of Princeton University and Prof. Takao Nishizeki of Tohoku University, contributed to this proceedings.

Interactive Proofs for Quantum Computationp. 1
Drawing Plane Graphsp. 2
Linear Time Algorithm for Approximating a Curve by a Single-Peaked Curvep. 6
A Dynamic Dictionary for Priced Information with Applicationp. 16
Voronoi Diagram in the Flow Fieldp. 26
Polygonal Path Approximation: A Query Based Approachp. 36
A Vertex Incremental Approach for Dynamically Maintaining Chordal Graphsp. 47
Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of Spanning Treesp. 58
Hotlink Enhancement Algorithms for Web Directoriesp. 68
Finding a Length-Constrained Maximum-Density Path in a Treep. 78
The Intractability of Computing the Hamming Distancep. 88
Infinitely-Often Autoreducible Setsp. 98
Limiting Negations in Bounded-Depth Circuits: An Extension of Markov's Theoremp. 108
Computational Complexity Measures of Multipartite Quantum Entanglementp. 117
A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphsp. 129
Polynomial Time 2-Approximation Algorithms for the Minmax Subtree Cover Problemp. 138
Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problemsp. 148
A New Translation from Semi-extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problemp. 158
The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problemsp. 168
Non-interactive Quantum Perfect and Statistical Zero-Knowledgep. 178
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?p. 189
A Faster Lattice Reduction Method Using Quantum Searchp. 199
Three Sorting Algorithms Using Priority Queuesp. 209
Lower Bounds on Correction Networksp. 221
Approximate Regular Expression Searching with Arbitrary Integer Weightsp. 230
Constructing Compressed Suffix Arrays with Large Alphabetsp. 240
On the Geometric Dilation of Finite Point Setsp. 250
On Computing All Immobilizing Grasps of a Simple Polygon with Few Contactsp. 260
Optimal Point Set Projections onto Regular Gridsp. 270
An Approximation Algorithm for Dissecting a Rectangle into Rectangles with Specified Areasp. 280
A Faster Algorithm for Two-Variable Integer Programmingp. 290
Efficient Algorithms for Generation of Combinatorial Covering Suitesp. 300
A Better Approximation for the Two-Machine Flowshop Scheduling Problem with Time Lagsp. 309
On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Datesp. 319
Online Scheduling of Parallel Jobs with Dependencies on 2-Dimensional Meshesp. 329
Efficient Algorithms for Descendent Subtrees Comparison of Phylogenetic Trees with Applications to Co-evolutionary Classifications in Bacterial Genomep. 339
Settling the Intractability of Multiple Alignmentp. 352
Efficient Algorithms for Optimizing Whole Genome Alignment with Noisep. 364
Segmenting Doughnut-Shaped Objects in Medical Imagesp. 375
On the Locality Properties of Space-Filling Curvesp. 385
Geometric Restrictions on Producible Polygonal Protein Chainsp. 395
Symmetric Layout of Disconnected Graphsp. 405
Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matchingp. 415
Enumerating Global Roundings of an Outerplanar Graphp. 425
Augmenting Forests to Meet Odd Diameter Requirementsp. 434
On the Existence and Determination of Satisfactory Partitions in a Graphp. 444
A Turn Function Scheme Realized in the Asynchronous Single-Writer/Multi-reader Shared Memory Modelp. 454
An Optimal Parallel Algorithm for c-Vertex-Ranking of Treesp. 464
The Student-Project Allocation Problemp. 474
Algorithms for Enumerating Circuits in Matroidsp. 485
A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Modelp. 495
Succinct Data Structures for Searchable Partial Sumsp. 505
Range Mode and Range Median Queries on Lists and Treesp. 517
Quasi-Perfect Minimally Adaptive q-ary Search with Unreliable Testsp. 527
New Ways to Construct Binary Search Treesp. 537
Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidthp. 544
Biconnectivity on Symbolically Represented Graphs: A Linear Solutionp. 554
A Dynamic Data Structure for Maintaining Disjoint Paths Information in Digraphsp. 565
Deterministic Algorithm for the t-Threshold Set Problemp. 575
Energy-Efficient Wireless Network Designp. 585
Wavelength Conversion in Shortest-Path All-Optical Networksp. 595
A Heuristic for the Stacker Crane Problem on Trees which Is Almost Surely Exactp. 605
Flexible Train Rosteringp. 615
Counting Complexity Classes over the Reals I: The Additive Casep. 625
Some Properties of One-Pebble Turning Machines with Sublogarithmic Spacep. 635
Hypergraph Decomposition and Secret Sharingp. 645
A Promising Key Agreement Protocolp. 655
Rapid Mixing of Several Markov Chains for a Hard-Core Modelp. 663
Polynomial Time Approximate Sampler for Discretized Dirichlet Distributionp. 676
Fair Cost Allocations under Conflicts - A Game-Theoretic Point of Viewp. 686
Equilibria for Networks with Malicious Usersp. 696
Quasi-optimal Arithmetic for Quaternion Polynomialsp. 705
Upper Bounds on the Complexity of Some Galois Theory Problemsp. 716
Unfolded Modular Multiplicationp. 726
Gauss Period, Sparse Polynomial, Redundant Basis, and Efficient Exponentiation for a Class of Finite Fields with Small Characteristicp. 736
Author Indexp. 747
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540206958
ISBN-10: 3540206957
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 748
Published: 3rd December 2003
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 3.91
Weight (kg): 1.06