**Preliminary Program of ISAAC'00**

Day 1: December 18 (Monday)

9:00-10:00 **Invited Talk by Jean-Daniel Boissonnat**

10:00-10:30 **Break**

10:30-12:00

Session 1(A): Algorithms and Data Structures

**Title:** Strategies for Hotlink Assignments

**Authors:** P. Bose, J. Czyzowicz, L. Gasieniec, E. Kranakis, D. Krizanc, A. Pelc, M. Martin

**Title:** A new competitive analysis of randomized caching

**Authors:** Ching Law and Charles E. Leiserson

**Title:** Online Routing in Convex Subdivisions

**Authors:** P. Bose, A. Brodnik, S. Carlsson, E. Demaine, R. Fleischer, A. Lopez-Ortiz, P. Morin, J. Munro

Session 1(B): Combinatorial Optimization

**Title:** A Simple Linear Time Approximation Algorithm for Multi-Processor Job Scheduling on Four Processors

**Authors:** Jingui Huang and Jianer Chen and Songqiao Chen

**Title:** Classification of Various Neighborhood Operations for the Nurse Scheduling Problem

**Authors:** Takayuki Osogami and Hiroshi Imai

**Title:** Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets

**Authors:** Yuyu Chen, Ming-Yang Kao, and Hsueh-I Lu

12:00-2:00 **Lunch**

2:00-3:30

Session 2(A): Algorithms and Data Structures

**Title:** Coping with delays and time-outs in binary search procedures

**Authors:** Ferdinando Cicalese and Ugo Vaccaro

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

**Authors:** Zhixiang Chen and Binhai Zhu

**Title:** Reasoning with Ordered Binary Decision Diagrams

**Authors:** Takashi HORIYAMA and Toshihide IBARAKI

Session 2(B): Approximation and Randomized Algorithms

**Title:** On Approximating Minimum Vertex Cover for Graphs with Perfect Matching

**Authors:** Jianer Chen and Iyad A. Kanj

**Title:** 2-Approximation algorithm for path coloring on trees of rings

**Authors:** X. Deng, G. Li, W. Zang, Y. Zhou

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

**Authors:** Q. S. Wu, C. L. Lu and R. C. T. Lee

3:30-4:00 **Break**

4:00-5:30

Session 3(A): Algorithms and Data Structures

**Title:** Finding Independent Spanning Trees in Partial k-Trees

**Authors:** Xiao Zhou and Takao Nishizeki

**Title:** On Efficient Fixed Parameter Algorithms for Weighted Vertex Cover

**Authors:** Rolf Niedermeier and Peter Rossmanith

**Title:** Constructive linear time algorithms for small cutwidth and carving-width

**Authors:** Dimitrios M. Thilikos, Maria J. Serna, and Hans L. Bodlaender

Session 3(B): Approximation and Randomized Algorithms

**Title:** Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits

**Authors:** Takao Asano, Magn\'us M. Halld\'orsson, Kazuo Iwama, and Takeshi Matsuda

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

**Authors:** Norihiro Kubo, Katsuhiro Muramoto, Shinichi Shimozono

**Title:** Simple algorithms for a weighted interval selection problem

**Authors:** Thomas Erlebach and Frits C.R. Spieksma

Day 2: Dec. 19 (Tuesday)

9:00-10:00 **Invited Talk by Jin-Yi Cai**

10:00-10:30 **Break**

10:30-12:00

Session 4(A): Graph Drawing and Algorithms

**Title:** Efficient Minus and Signed Domination in Graphs

**Authors:** Chin Lung Lu and Sheng-Lung Peng and Chuan Yi Tang

**Title:** Convex Grid Drawings of Four-Connected Plane Graphs

**Authors:** Kazuyuki Miura, Shin-ichi Nakano and Takao Nishizeki

**Title:** An Algorithm for Finding Three Dimensional Symmetry in Series Parallel Digraphs

**Authors:** Seok-Hee Hong and Peter Eades

Session 4(B): Automata, Cryptography, and Complexity Theory

**Title:** Undecidability results for monoids with linear-time decidable word problems

**Authors:** M. Katsura, Y. Kobayashi, F. Otto

**Title:** Secret Key Exchange Using Random Deals of Cards on Hierarchical Structures

**Authors:** Reina Yoshikawa, Shimin Guo, Kazuhiro Motegi, and Yoshihide Igarashi

**Title:** Derandomizing Arthur-Merlin games under uniform assumptions

**Authors:** Chi-Jen Lu

12:00-2:00 **Lunch**

2:00-3:30

Session 5(A): Algorithms and Data Structures

**Title:** A Near Optimal Algorithm for Vertex Connectivity Augmentation

**Authors:** Bill Jackson and Tibor Jordan

**Title:** Simultaneous Augmentation of Two Graphs to an $\ell$-Edge-Connected Graph and a Biconnected Graph

**Authors:** Toshimasa Ishii and Hiroshi Nagamochi

**Title:** Location problems based on node-connectivity and edge-connectivity between nodes and node-subsets

**Authors:** Hiro Ito, Motoyasu Ito, Yuichirou Itatsu, Hideyuki Uehara, and Mitsuo Yokoyama

Session 5(B): Parallel and Distributed Algorithms

**Title:** An Intuitive and Effective New Representation for Interconnection Network Structures

**Authors:** Jianer Chen and Weijia Jia and Lihua Liu and Songqiao Chen

**Title:** Randomized Leader Election Protocols in Radio Networks with no Collision Detection

**Authors:** Koji Nakano and Stephan Olariu

**Title:** Deterministic broadcasting time with partial knowledge of the network

**Authors:** Gianluca De Marco and Andrzej Pelc

3:30-4:00 **Break**

4:00-5:30

Session 6(A): Algorithms and Data Structures

**Title:** Minimizing Makespan in Batch Machine Scheduling

**Authors:** Chung Keung Poon and Pixing Zhang

**Title:** Preemptive Parallel Task Scheduling in O(n)+poly(m) Time

**Authors:** Klaus Jansen and Lorant Porkolab

**Title:** Compressed Text Databases with Efficient Query Algorithms based on the Comressed Suffix Array

**Authors:** Kunihiko Sadakane

Session 6(B): Computational Geometry

**Title:** A Better Lower Bound for Two-Circle Point Labeling

**Authors:** Alexander Wolff and Michael Thon and Yinfeng Xu

**Title:** Voronoi diagram of a circle set constructed from Voronoi diagram of a point set

**Authors:** Deok-Soo Kim, Donguk Kim and Kokichi Sugihara

**Title:** An Improved Algorithm for Subdivision Traversal without Extra Storage

**Authors:** Prosenjit Bose and Pat Morin

Day 3: Dec. 20 (Wednesday)

9:00-10:30

Session 7(A): Algorithms and Data Structures

**Title:** Generalized H-coloring of graphs

**Authors:** Petter Kristiansen and Jan Arne Telle

**Title:** Finding a Two-Core of a Tree in Linear Time

**Authors:** Biing-Feng Wang and Jyh-Jye Lin

**Title:** Unbalanced and Hierarchical Bipartite Matchings with Applications to Labeled Tree Comparsion

**Authors:** Ming-Yang Kao and Tak-Wah Lam and Wing-Kin Sung and Hing-Fung Ting

Session 7(B): Computational Geometry

**Title:** Optimal Beam Penetrations in Two and Three Dimensions

**Authors:** Danny Z. Chen, Xiaobo (Sharon) Hu, and Jinhui Xu

**Title:** Searching a Simple Polygon by a k-Searcher

**Authors:** Xuehou TAN

**Title:** Characterization of Rooms Searchable by Two Guards

**Authors:** Sang-Min Park, Jae-Ha Lee, Kyung-Yong Chwa

10:30-11:00 **Break**

11:00-12:00

Session 8(A): Computational Biology

**Title:** Improved Phylogeny Comparisons: Non-Shared Edges, Nearest Neighbor Interchanges, and Subtree Transfers

**Authors:** Wing-Kai Hon, Ming-Yang Kao and Tak-Wah Lam

**Title:** Phylogenetic $k$-Root and Steiner $k$-Root

**Authors:** Guo-Hui Lin and Paul E. Kearney and Tao Jiang

Session 8(B): Computational Geometry

**Title:** Maintenance of a Piercing Set for Intervals with Applications

**Authors:** Matthew J. KATZ, Frank NIELSEN and Michael SEGAL

**Title:** Optimal Polygon Cover Problems and Applications

**Authors:** Danny Z. Chen, Xiaobo (Sharon) Hu, and Xiaodong Wu

12:30-2:00 **Lunch**

Excursion