11. ISAAC 2000: Taipei, Taiwan

Invited Presentations

• Jean-Daniel Boissonnat:
  Voronoi-Based Systems of Coordinates and Surface Reconstruction. 1
  
• Jin-yi Cai:
  Essentially Every Unimodular Matrix Defines and Expander. 2-22
  

Algorithms and Data Structures (I)

• Prosenjit Bose, Evangelos Kranakis, Danny Krizanc, Miguel Vargas Martin, Jurek Czyzowicz, Andrzej Pelc, Leszek Gasieniec:
  Strategies for Hotlink Assignments. 23-34
  
• Ching Law, Charles E. Leiserson:
  A New Competitive Analysis of Randomized Caching. 35-46
  
• Prosenjit Bose, Pat Morin, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, J. Ian Munro, Alejandro López-Ortiz:
  Online Routing in Convex Subdivisions. 47-59
  

Combinatorial Optimization

• Jingui Huang, Jianer Chen, Songqiao Chen:
  A Simple Linear-Time Approximation Algorithm for Multi-processor Job Scheduling on Four Processors. 60-71
  
• Takayuki Osogami, Hiroshi Imai:
  Classification of Various Neighborhood Operations for the Nurse Scheduling Problem. 72-83
  
• Yuyu Chen, Ming-Yang Kao, Hsueh-I Lu:
  Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets. 84-95
  

Algorithms and Data Structures (II)

• Ferdinando Cicalese, Ugo Vaccaro:
  coping with Delays and Time-Outs in Binary Search Procedures. 96-107
  
• Zhixiang Chen, Binhai Zhu:
  Some Formal Analysis of Roccio's Similarity-Based Relvance Feedback Algorithm. 108-119
  
• Takashi Horiyama, Toshihide Ibaraki:
  Reasoning with Ordered Binary Decision Diagrams. 120-131
  

Approximation and Randomized Algorithms (I)

• Jianer Chen, Iyad A. Kanj:
  On Approximating Minimum Vertex Cover for Graphs with Perfect Matching. 132-143
  
• Xiaotie Deng, Yi Zhou, Guojun Li, Wenan Zang:
  A 2-Approximation Algorithm for Path Coloring on Trees of Rings. 144-155
  
• Q. S. Wu, Chin Lung Lu, Richard C. T. Lee:
  An Approximate Algorithm for the Weighted Hamiltonian Path Completion Problem on a Tree. 156-167
  

Algortihms and Data Structures (III)

• Xiao Zhou, Takao Nishizeki:
  Finding Independent Spanning Trees in Partial k-Trees. 168-179
  
• Rolf Niedermeier, Peter Rossmanith:
  On Efficient Fixed Parameter Algorithms for WEIGHTED VERTEX COVER. 180-191
  
• Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender:
  Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width. 192-203
  

Approximation and Randomized Algorithms (II)

• Takao Asano, Magnús M. Halldórsson, Kazuo Iwama, Takeshi Matsuda:
  Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits. 204-215
  
• Norihiro Kubo, Shinichi Shimozono, Katsuhiro Muramoto:
  A Simple and Quick Approximation Algorithm for Traveling Salesman Problem in the Plane. 216-227
  
• Thomas Erlebach, Frits C. R. Spieksma:
  Simple Algorithms for a Weighted Interval Selection Problem. 228-240
  

Graph Drawing and Algorithms

• Chin Lung Lu, Sheng-Lung Peng, Chuan Yi Tang:
  Efficient Minus and Signed Domination in Graphs. 241-253
  
• Kazuyuki Miura, Takao Nishizeki, Shin-Ichi Nakano:
  Convex Grid Drwaings of Four-Connected Plane Graphs. 254-265
  
• Seok-Hee Hong, Peter Eades:
  An Algorithm for Finding Three Dimensional Symmetry in Series Parallel Digraphs. 266-277
  

Automata, Cryptography, and Complexity Theory

• Masashi Katsura, Yuji Kobayashi, Friedrich Otto:
  Undecidability Results for Monoids with Linear-Time Decidable Word Problems. 278-289
  
• Reina Yoshikawa, Shimin Guo, Kazuhiro Motegi, Yoshihide Igarashi:
  Secret Key Exchange Using Random Deals of Cards on Hierarchical Structures. 290-301
  
• Chi-Jen Lu:
  Derandomizing Arthur-Merlin Games under Uniform Assumptions. 302-312
  

Algorithms and Data Structures (IV)

• Bill Jackson, Tibor Jordán:
  A Near Optimal Algorithm for Vertex Connectivity Augmentation. 312-325
  
• Toshimasa Ishii, Hiroshi Nagamochi:
  Simultaneous Augmentation of Two Graphs to an l-Edge-Connected Graph and a Biconnected Graph. 326-337
  
• Hiro Ito, Yuichiro Itatsu, Hideyuki Uehara, Mitsuo Yokoyama, Motoyasu Ito:
  Location Problems Based on Node-Connectivity and Edge-Connectivity between Nodes and Node-Subsets. 338-349
  

Parallel and Distributed Algorithms

• Jianer Chen, Lihua Liu, Songqiao Chen, Weijia Jia:
  An Intuitive and Effective New Representation for Interconnection Network Structures. 350-361
  
• Koji Nakano, Stephan Olariu:
  Randomized Leader Election Protocols in Radio Networks with No Collision Detection. 362-373
  
• Gianluca De Marco, Andrzej Pelc:
  Deterministic Broadcasting Time with Partial Knowledge of the Network. 374-385
  

Algorithms and Data Structures (V)

• Chung Keung Poon, Pixing Zhang:
  Minimizing Makespan in Batch Machine Scheduling. 386-397
  
• Klaus Jansen, Lorant Porkolab:
  Preemptive Parallel Task Scheduling in O(n)+Poly(m) Time. 398-409
  
• Kunihiko Sadakane:
  Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array. 410-421
  

Computational Geometry (I)

• Alexander Wolff, Michael Thon, Yin-Feng Xu:
  A Better Lower Bound for Two-Circle Point Labeling. 422-431
  
• Deok-Soo Kim, Donguk Kim, Kokichi Sugihara:
  Voronoi Diagram of a Circle Set Constructed from Voronoi Diagram of a Point Set. 432-443
  
• Prosenjit Bose, Pat Morin:
  An Improved Algorithm for Subdivision Traversal without Extra Storage. 444-455
  

Algorithms and Data Structures (VI)

• Petter Kristiansen, Jan Arne Telle:
  Generalized H-Coloring of Graphs. 456-466
  
• Biing-Feng Wang, Jyh-Jye Lin:
  Finding a Two-Core of a Tree in Linear Time. 467-478
  
• Ming-Yang Kao, Tak Wah Lam, Wing-Kin Sung, Hing-Fung Ting:
  Unbalanced and Hierarchical Bipartite Matchings with Applications to Labeled Tree Comparison. 479-490
  

Computational Geometry (II)

• Danny Z. Chen, Xiaobo Hu, Jinhui Xu:
  Optimal Beam Penetrations in Two and Three Dimensions. 491-502
  
• Xuehou Tan:
  Searching a Simple Polygon by a k-Searcher. 503-514
  
• Sang-Min Park, Kyung-Yong Chwa, Jae-Ha Lee:
  Characterization of Rooms Searchable by Two Guards. 515-526
  

Computational Biology

• Wing-Kai Hon, Ming-Yang Kao, Tak Wah Lam:
  Improved Phylogeny Comparisons: Non-shared Edges, Nearest Neighbor Interchanges, and Subtree Transfers. 527-538
  
• Guo-Hui Lin, Tao Jiang, Paul E. Kearney:
  Phylogenetic k-Root and Steiner k-Root. 539-551
  

Computational Geometry (III)

• Matthew J. Katz, Frank Nielsen, Michael Segal:
  Maintenance of a Percing Set for Intervals with Applications. 552-563
  
• Danny Z. Chen, Xiaobo Hu, Xiaodong Wu:
  Optimal Polygon Cover Problems and Applcations. 564-576