Algorithms and Computation : 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings / edited by Toshihide Ibaraki, Naoki Katoh, Hirotaka Ono.

Format:

Book

Contributor:

Ibaraki, Toshihide, editor.

Katoh, Naoki, editor.

Ono, Hirotaka, editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

Lecture notes in computer science 0302-9743 ; 2906.

Lecture Notes in Computer Science, 0302-9743 ; 2906

Language:

English

Subjects (All):

Computer programming.

Algorithms.

Computer networks.

Computers.

Computer science--Mathematics.

Computer science.

Computer graphics.

Programming Techniques.

Algorithm Analysis and Problem Complexity.

Computer Communication Networks.

Computation by Abstract Devices.

Discrete Mathematics in Computer Science.

Computer Graphics.

Local Subjects:

Programming Techniques.

Algorithm Analysis and Problem Complexity.

Computer Communication Networks.

Computation by Abstract Devices.

Discrete Mathematics in Computer Science.

Computer Graphics.

Physical Description:

1 online resource (XVII, 748 pages).

Edition:

First edition 2003.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2003.

System Details:

text file PDF

Summary:

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.

Contents:

Invited Talk

Interactive Proofs for Quantum Computation

Drawing Plane Graphs

1A Computational Geometry I

Linear Time Algorithm for Approximating a Curve by a Single-Peaked Curve

A Dynamic Dictionary for Priced Information with Application

Voronoi Diagram in the Flow Field

Polygonal Path Approximation: A Query Based Approach

1B Graph and Combinatorial Algorithms I

A Vertex Incremental Approach for Dynamically Maintaining Chordal Graphs

Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of Spanning Trees

Hotlink Enhancement Algorithms for Web Directories

Finding a Length-Constrained Maximum-Density Path in a Tree

2A Computational Complexity I

The Intractability of Computing the Hamming Distance

Infinitely-Often Autoreducible Sets

Limiting Negations in Bounded-Depth Circuits: An Extension of Markov's Theorem

Computational Complexity Measures of Multipartite Quantum Entanglement

2B Graph and Combinatorial Algorithms II

A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs

Polynomial Time 2-Approximation Algorithms for the Minmax Subtree Cover Problem

Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-Hard Problems

A New Translation from Semi-extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problem

3A Quantum Computation

The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems

Non-interactive Quantum Perfect and Statistical Zero-Knowledge

Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?

A Faster Lattice Reduction Method Using Quantum Search

3B Graph and Combinatorial Algorithms III

Three Sorting Algorithms Using Priority Queues

Lower Bounds on Correction Networks

Approximate Regular Expression Searching with Arbitrary Integer Weights

Constructing Compressed Suffix Arrays with Large Alphabets

4A Computational Geometry II

On the Geometric Dilation of Finite Point Sets

On Computing All Immobilizing Grasps of a Simple Polygon with Few Contacts

Optimal Point Set Projections onto Regular Grids

4B Combinatorial Optimization I

An Approximation Algorithm for Dissecting a Rectangle into Rectangles with Specified Areas

A Faster Algorithm for Two-Variable Integer Programming

Efficient Algorithms for Generation of Combinatorial Covering Suites

5A Scheduling

A Better Approximation for the Two-Machine Flowshop Scheduling Problem with Time Lags

On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Dates

Online Scheduling of Parallel Jobs with Dependencies on 2-Dimensional Meshes

5B Computational Biology

Efficient Algorithms for Descendent Subtrees Comparison of Phylogenetic Trees with Applications to Co-evolutionary Classifications in Bacterial Genome

Settling the Intractability of Multiple Alignment

Efficient Algorithms for Optimizing Whole Genome Alignment with Noise

6A Computational Geometry III

Segmenting Doughnut-Shaped Objects in Medical Images

On the Locality Properties of Space-Filling Curves

Geometric Restrictions on Producible Polygonal Protein Chains

Symmetric Layout of Disconnected Graphs

6B Graph and Combinatorial Algorithms IV

Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matching

Enumerating Global Roundings of an Outerplanar Graph

Augmenting Forests to Meet Odd Diameter Requirements

On the Existence and Determination of Satisfactory Partitions in a Graph

7A Distributed and Parallel Algorithms

A Turn Function Scheme Realized in the Asynchronous Single-Writer/Multi-reader Shared Memory Model

An Optimal Parallel Algorithm for c-Vertex-Ranking of Trees

7B Graph and Combinatorial Algorithms V

The Student-Project Allocation Problem

Algorithms for Enumerating Circuits in Matroids

A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model

8A Data Structure

Succinct Data Structures for Searchable Partial Sums

Range Mode and Range Median Queries on Lists and Trees

Quasi-Perfect Minimally Adaptive q-ary Search with Unreliable Tests

New Ways to Construct Binary Search Trees

8B Graph and Combinatorial Algorithms VI

Improved Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth

Biconnectivity on Symbolically Represented Graphs: A Linear Solution

A Dynamic Data Structure for Maintaining Disjoint Paths Information in Digraphs

Deterministic Algorithm for the t-Threshold Set Problem

9A Combinatorial and Network Optimization

Energy-Efficient Wireless Network Design

Wavelength Conversion in Shortest-Path All-Optical Networks

A Heuristic for the Stacker Crane Problem on Trees Which Is Almost Surely Exact

Flexible Train Rostering

9B Computational Complexity and Cryptography

Counting Complexity Classes over the Reals I: The Additive Case

Some Properties of One-Pebble Turing Machines with Sublogarithmic Space

Hypergraph Decomposition and Secret Sharing

A Promising Key Agreement Protocol

10A Game Theory and Randomized Algorithm

Rapid Mixing of Several Markov Chains for a Hard-Core Model

Polynomial Time Approximate Sampler for Discretized Dirichlet Distribution

Fair Cost Allocations under Conflicts - A Game-Theoretic Point of View -

Equilibria for Networks with Malicious Users

10B Algebraic and Arithmetic Computation

Quasi-optimal Arithmetic for Quaternion Polynomials

Upper Bounds on the Complexity of Some Galois Theory Problems

Unfolded Modular Multiplication

Gauss Period, Sparse Polynomial, Redundant Basis, and Efficient Exponentiation for a Class of Finite Fields with Small Characteristic.

Other Format:

Printed edition:

ISBN:

978-3-540-24587-2

9783540245872

Access Restriction:

Restricted for use by site license.