Algorithms and Computation : 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000. Proceedings / edited by D.T. Lee, Shang-Hua Teng.

Format:

Book

Contributor:

Lee, Der-Tsai, editor.

Teng, Shang-Hua, editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

Lecture notes in computer science 0302-9743 ; 1969.

Lecture Notes in Computer Science, 0302-9743 ; 1969

Language:

English

Subjects (All):

Data structures (Computer science).

Computers.

Computer programming.

Algorithms.

Computer networks.

Data Structures and Information Theory.

Theory of Computation.

Programming Techniques.

Algorithm Analysis and Problem Complexity.

Computation by Abstract Devices.

Computer Communication Networks.

Local Subjects:

Data Structures and Information Theory.

Theory of Computation.

Programming Techniques.

Algorithm Analysis and Problem Complexity.

Computation by Abstract Devices.

Computer Communication Networks.

Physical Description:

1 online resource (XIV, 582 pages).

Edition:

First edition 2000.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2000.

System Details:

text file PDF

Summary:

The papers in this volume were selected for presentation at the Eleventh Annual International Symposium on Algorithms and Computation (ISAAC 2000), held on 18{20 December, 2000 at the Institute of Information Science, Academia Sinica, Taipei, Taiwan. Previous meetings were held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), and Chennai (1999). Submissions to the conference this year were conducted entirely electro- cally. Thanks to the excellent software developed by the Institute of Information Science, Academia Sinica, we were able to carry out virtually all communication via the World Wide Web. In response to the call for papers, a total of 87 extended abstracts were submitted from 25 countries. Each submitted paper was handled by at least three program committee members, with the assistance of a number of external reviewers, as indicated by the referee list found in the proceedings. There were many more acceptable papers than there was space available in the symposium program, which made the program committee's task extremely di cult. Finally 46 papers were selected for presentation at the Symposium. In addition to these contributed papers, the conference also included two invited presentations by Dr. Jean-Daniel Boissonnat, INRIA Sophia-Antipolis, France and Professor Jin-Yi Cai, University of Wisconsin at Madison, Wisconsin, USA. It is expected that most of the accepted papers will appear in a more complete form in scienti c journals.

Contents:

Invited Presentations

Voronoi-Based Systems of Coordinates and Surface Reconstruction

Essentially Every Unimodular Matrix Defines an Expander

Algorithms and Data Structures (I)

Strategies for Hotlink Assignments

A New Competitive Analysis of Randomized Caching

Online Routing in Convex Subdivisions

Combinatorial Optimization

A Simple Linear-Time Approximation Algorithm for Multi-processor Job Scheduling on Four Processors

Classification of Various Neighborhood Operations for the Nurse Scheduling Problem

Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets

Algorithms and Data Structures (II)

Coping with Delays and Time-Outs in Binary Search Procedures

Some Formal Analysis of Rocchio's Similarity-Based Relevance Feedback Algorithm

Reasoning with Ordered Binary Decision Diagrams

Approximation and Randomized Algorithms (I)

On Approximating Minimum Vertex Cover for Graphs with Perfect Matching

A 2-Approximation Algorithm for Path Coloring on Trees of Rings

An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree

Algorithms and Data Structures (III)

Finding Independent Spanning Trees in Partial k-Trees

On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover

Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width

Approximation and Randomized Algorithms (II)

Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits

A Simple and Quick Approximation Algorithm for Traveling Salesman Problem in the Plane

Simple Algorithms for a Weighted Interval Selection Problem

Graph Drawing and Algorithms

Efficient Minus and Signed Domination in Graphs

Convex Grid Drawings of Four-Connected Plane Graphs

An Algorithm for Finding Three Dimensional Symmetry in Series Parallel Digraphs

Automata, Cryptography, and Complexity Theory

Undecidability Results for Monoids with Linear-Time Decidable Word Problems

Secret Key Exchange Using Random Deals of Cards on Hierarchical Structures

Derandomizing Arthur-Merlin Games under Uniform Assumptions

Algorithms and Data Structures (IV)

A Near Optimal Algorithm for Vertex Connectivity Augmentation

Simultaneous Augmentation of Two Graphs to an ?Edge-Connected Graph and a Biconnected Graph

Location Problems Based on Node-Connectivity and Edge-Connectivity between Nodes and Node-Subsets

Parallel and Distributed Algorithms

An Intuitive and Effective New Representation for Interconnection Network Structures

Randomized Leader Election Protocols in Radio Networks with no Collision Detection

Deterministic Broadcasting Time with Partial Knowledge of the Network

Algorithms and Data Structures (V)

Minimizing Makespan in Batch Machine Scheduling

Preemptive Parallel Task Scheduling in O(n) + Poly(m) Time

Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array

Computational Geometry (I)

A Better Lower Bound for Two-Circle Point Labeling

Voronoi Diagram of a Circle Set Constructed from Voronoi Diagram of a Point Set

An Improved Algorithm for Subdivision Traversal without Extra Storage

Algorithms and Data Structures (VI)

Generalized H-Coloring of Graphs

Finding a Two-Core of a Tree in Linear Time

Unbalanced and Hierarchical Bipartite Matchings with Applications to Labeled Tree Comparison

Computational Geometry (II)

Optimal Beam Penetrations in Two and Three Dimensions

Searching a Simple Polygon by a k-Searcher

Characterization of Rooms Searchable by Two Guards

Computational Biology

Improved Phylogeny Comparisons: Non-shared Edges, Nearest Neighbor Interchanges, and Subtree Transfers

Phylogenetic k-Root and Steiner k-Root

Computational Geometry (III)

Maintenance of a Piercing Set for Intervals with Applications

Optimal Polygon Cover Problems and Applications.

Other Format:

Printed edition:

ISBN:

978-3-540-40996-0

9783540409960

Access Restriction:

Restricted for use by site license.