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