image

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