Hsueh-I Lu hil at
Wed Nov 8 11:36:37 PST 2000

11th Annual International Symposium on Algorithms and Computation 
			December 18--20, 2000
		   Institute of Information Science
			   Academia Sinica
			    Taipei, Taiwan

Program Committee
  Co-chair: D. T. Lee, Academia Sinica
  Co-chair: Shang-Hua Teng, Univ. of Illinois
  Helmut Alt, Free University of Berlin
  Nina Amenta, Univ. of Texas at Austin
  Gen-Huey Chen, National Taiwan Univ.
  Giuseppe Italiano, University of Rome
  Kazuo Iwama, Kyoto University
  Marcos Kiwi, University of Chile
  Jeff Erickson, University of Illinois
  Ming-Tat Ko, Academia Sinica
  Kurt Mehlhorn, Max Planck Institute
  Michael D. Mitzenmacher, Harvard Univ.
  Kunsoo Park, Seoul National University
  Tadao Takaoka, University of Canterbury
  Takeshi Tokuyama, Sendi University
  Peng-Jun Wan, Illinois Inst. of Technology
  Derick Wood, Hong Kong Univ. Sci. and Tech.

Invited Talks
(1) Voronoi-Based Systems of Coordinates and Surface Reconstruction,
Jean-Daniel Boissonnat (INRIA, Unit\'e de Sophia Antipolis)

(2) Essentially Every Unimodular Matrix Defines an Expander,
Jin-Yi Cai (State University of New York at Buffalo, University of

Monday, December 18
[9:00--10:00] Invited Talk (1)
[10:30--12:00] 1A: Algorithms and Data Structures
Strategies for Hotlink Assignments
(P. Bose, J. Czyzowicz, L. Gasieniec, E. Kranakis, D. Krizanc,
A. Pelc, M. Martin)

A New Competitive Analysis of Randomized Caching
(C. Law and C. E. Leiserson)

Online Routing in Convex Subdivisions
(P. Bose, A. Brodnik, S. Carlsson, E. Demaine, R. Fleischer,
A. Lopez-Ortiz, P. Morin, J. Munro)

[12:30--12:00] 1B: Combinatorial Optimization
A Simple Linear-Time Approximation Algorithm for Multi-processor Job
Scheduling on Four Processors   
(J. Huang, J. Chen, S. Chen)

Classification of Various Neighborhood Operations for the Nurse
Scheduling Problem 
(T. Osogami, H. Imai)

Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets
(Y. Chen, M.-Y. Kao, H.-I. Lu)

[2:30--3:30] 2A: Algorithms and Data Structures
Coping with Delays and Time-Outs in Binary Search Procedures
(F. Cicalese, U. Vaccaro)

Some Formal Analysis of Rocchio's Similarity-Based Relevance Feedback
(Z. Chen, B. Zhu)

Reasoning with Ordered Binary Decision Diagrams
(T. Horiyama, T. Ibaraki)

[2:30--3:30] 2B: Approximation and Randomized Algorithms
On Approximating Minimum Vertex Cover for Graphs with Perfect Matching
(J. Chen, I. A. Kanj)

2-Approximation Algorithm for Path Coloring on Trees of Rings
(X. Deng, G. Li, W. Zang, Y. Zhou)

An Approximate Algorithm for the Weighted Hamiltonian Path Completion
Problem on a Tree 
(Q. S. Wu, C. L. Lu, R. C. T. Lee)

[4:00--5:30] 3A: Algorithms and Data Structures
Finding Independent Spanning Trees in Partial $k$-Trees
(X. Zhou, T. Nishizeki)

On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover
(R. Niedermeier, P. Rossmanith)

Constructive Linear-Time Algorithms for Small Cutwidth and Carving-Width
(D. M. Thilikos, M. J. Serna, H. L. Bodlaender)

[4:00--5:30] 3B:  Approximation and Randomized Algorithms
Approximation Algorithms for the Maximum Power Consumption Problem on
Combinatorial Circuits 
(T. Asano, M. M. Halld\'orsson, K. Iwama, T. Matsuda )

A Simple and Quick Approximation Algorithm for Traveling Salesman
Problem in the Plane 
(N. Kubo, K. Muramoto, S. Shimozono)

Simple Algorithms for a Weighted Interval Selection Problem
(T. Erlebach, F. C.R. Spieksma)

Tuesday, December 19

[9:00-10:00] Invited Talk (2)
[10:30--12:00] 4A: Graph Drawing and Algorithms
Efficient Minus and Signed Domination in Graphs
(C. L. Lu, S.-L. Peng, C. Y. Tang)

Convex Grid Drawings of Four-Connected Plane Graphs
(K. Miura, S.-i. Nakano, T. Nishizeki)

An Algorithm for Finding Three-Dimensional Symmetry in Series-Parallel
(S.-H. Hong, P. Eades)

[10:30--12:00] 4B: Automata, Cryptography, and Complexity Theory
Undecidability Results for Monoids with Linear-Time Decidable Word
(M. Katsura, Y. Kobayashi, F. Otto)

Secret Key Exchange Using Random Deals of Cards on Hierarchical
(R. Yoshikawa, S. Guo, K. Motegi, Y. Igarashi)

Derandomizing Arthur-Merlin Games under Uniform Assumptions
(C.-J. Lu)

[2:00--3:30] 5A: Algorithms and Data Structures
A Near Optimal Algorithm for Vertex Connectivity Augmentation
(B. Jackson, T. Jordan)

Simultaneous Augmentation of Two Graphs to an $\ell$-Edge-Connected
Graph and a Biconnected Graph 
(T. Ishii, H. Nagamochi)

Location Problems Based on Node-Connectivity and Edge-Connectivity
between Nodes and Node-Subsets
(H. Ito, M. Ito, Y. Itatsu, H. Uehara, M. Yokoyama)

[2:00--3:30] 5B: Parallel and Distributed Algorithms
An Intuitive and Effective New Representation for Interconnection
Network Structures
(J. Chen, W. Jia, L. Liu, S. Chen)

Randomized Leader Election Protocols in Radio Networks with no
Collision Detection 
(K. Nakano, S. Olariu)

Deterministic Broadcasting Time with Partial Knowledge of the Network
(G. De~Marco, A. Pelc)

[4:00-5:30] 6A: Algorithms and Data Structures
Minimizing Makespan in Batch Machine Scheduling
(C. K. Poon, P. Zhang)

Preemptive Parallel Task Scheduling in $O(n)+\mboxpoly(m)$ Time
(K. Jansen, L. Porkolab)

Compressed Text Databases with Efficient Query Algorithms based on the
Comressed Suffix Array
(K. Sadakane)

[4:00-5:30] 6B: Computational Geometry
A Better Lower Bound for Two-Circle Point Labeling
(A. Wolff, M. Thon, Y. Xu)

Voronoi Diagram of a Circle Set Constructed from Voronoi Diagram of a 
Point Set
(D.-S. Kim, D. Kim, K. Sugihara)

An Improved Algorithm for Subdivision Traversal without Extra Storage
(P. Bose, P. Morin)

Wednesday, December 20

[9:00-10:30] 7A: Algorithms and Data Structures
Generalized H-coloring of Graphs
(P. Kristiansen, J. A. Telle)

Finding a Two-Core of a Tree in Linear Time
(B.-F. Wang, J.-J. Lin)

Unbalanced and Hierarchical Bipartite Matchings with Applications to
Labeled Tree Comparsion 
(M.-Y. Kao, T.-W. Lam, W.-K. Sung, H.-F. Ting)

[9:00-10:30] 7B: Computational Geometry
Optimal Beam Penetrations in Two and Three Dimensions
(D. Z. Chen, X. (S.) Hu, J. Xu)

Searching a Simple Polygon by a $k$-searcher
(X. Tan)

Characterization of Rooms Searchable by Two Guards
(S.-M. Park, J.-H. Lee, K.-Y. Chwa)

[11:00--12:00] 8A: Computational Biology
Improved Phylogeny Comparisons: Non-Shared Edges, Nearest Neighbor
Interchanges, and Subtree Transfers 
(W.-K. Hon, M.-Y. Kao, T.-W. Lam)

Phylogenetic $k$-Root and Steiner $k$-Root
(G.-H. Lin, P. E. Kearney, T. Jiang)

[11:00--12:00] 8B: Computational Geometry
Maintenance of a Piercing Set for Intervals with Applications
(M. J. Katz, F. Nielsen, M. Segal)

Optimal Polygon Cover Problems and Applications
(D. Z. Chen, X. (S.) Hu, X. Wu)

[2:00--] Excursion

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list