ADVANCE PROGRAM OF ISAAC'00, TAIPEI, TAIWAN

Wed Nov 8 11:36:37 PST 2000

11th Annual International Symposium on Algorithms and Computation 
			      (ISAAC'00)
			December 18--20, 2000
		   Institute of Information Science
			   Academia Sinica
			    Taipei, Taiwan
		http://www.iis.sinica.edu.tw/isaac00/

=================
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
Wisconsin)

===============
ADVANCE PROGRAM
===============
-------------------
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
Algorithm 
(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
Digraphs 
(S.-H. Hong, P. Eades)

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

Secret Key Exchange Using Random Deals of Cards on Hierarchical
Structures
(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
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/maillist.html.