12. ISAAC 2001: Christchurch, New Zealand

Invited Talk 1

• Sue Whitesides:
  Chain Reconfiguration. The INs and Outs, Ups and Downs of Moving Polygons and Polygonal Linkages. 1-13
  

Combinatorial Generation and Optimization (I)

• Kazuo Murota, Akihisa Tamura:
  Application of M-Convex Submodular Flow Problem to Mathematical Economics. 14-25
  
• Xiaotie Deng, Haodi Feng, Pixing Zhang, Hong Zhu:
  A Polynomial Time Approximation Scheme for Minimizing Total Completion Time of Unbounded Batch Scheduling. 26-35
  
• Yoshiyuki Karuno, Hiroshi Nagamochi:
  A Polynomial Time Approximation Scheme for the Multi-vehicle Scheduling Problem on a Path with Release and Handling Times. 36-47
  
• Jianer Chen, Jingui Huang:
  Semi-normal Schedulings: Improvement on Goemans' Algorithm. 48-60
  

Parallel and Distributed Algorithms (I)

• Hisashi Koga:
  Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness. 61-73
  
• Jae-Hoon Kim, Kyung-Yong Chwa:
  Broadcasting with Universal Lists Revisited: Using Competitive Analysis. 74-85
  
• Kumiko Nomura, Toshinori Yamada, Shuichi Ueno:
  On Adaptive Fault Diagnosis for Multiprocessor Systems. 86-98
  
• Kenta Hashimoto, Toshinori Yamada, Shuichi Ueno:
  On-Line Multicasting in All-Optical Networks. 99-106
  

Graph Drawing and Algorithms (I)

• Shin-Ichi Nakano:
  Enumerating Floorplans with n Rooms. 107-115
  
• Giulia Galbiati:
  On Min-Max Cycle Bases. 116-123
  
• Hiroshi Nagamochi, Toshimasa Ishii:
  On the Minimum Local-Vertex-Connectivity Augmentation in Graphs. 124-135
  
• Takayuki Nagoya:
  Counting Graph Isomorphisms among Chordal Graphs with Restricted Clique Number. 136-147
  

Computational Geometry (I)

• Kunihiko Sadakane, Norito Sugawara, Takeshi Tokuyama:
  Quantum Algorithms for Intersection and Proximity Problems. 148-159
  
• Zheng Sun, John H. Reif:
  BUSHWHACK: An Approximation Algorithm for Minimal Paths through Pseudo-Euclidean Spaces. 160-171
  
• Francis Y. L. Chin, Stanley P. Y. Fung:
  Approximation of Minimum Triangulation for Polyhedron with Bounded Degrees. 172-184
  
• Christian Schindelhauer, Birgitta Weber:
  Tree-Approximations for the Weighted Cost-Distance Problem. 185-195
  

Computational Complexity and Cryptology

• Takaaki Mizuki, Takao Nishizeki:
  Necessary and Sufficient Numbers of Cards for Sharing Secret Keys on Hierarchical Groups. 196-207
  
• Akihiro Yamamura, Kaoru Kurosawa:
  Generic Algorithms and Key Agreement Protocols Based on Group Actions. 208-218
  
• Josef M. Breutzmann, David W. Juedes, Jack H. Lutz:
  Baire Category and Nowhere Differentiability for Feasible Real Functions. 219-230
  
• Takashi Horiyama, Toshihide Ibaraki:
  Translation among CNFs, Characteristic Models and Ordered Binary Decision Diagrams. 231-243
  

Automata and Formal Languages

• Oscar H. Ibarra, Zhe Dang:
  On Removing the Pushdown Stack in Reachability Constructions. 244-256
  
• Hiroaki Yamamoto:
  A New Recognition Algorithm for Extended Regular Expressions. 257-267
  
• Takeshi Koshiba:
  Polynomial-Time Algorithms for the Equivalence for One-Way Quantum Finite Automata. 268-278
  
• Hirotaka Ono, Mutsunori Yagiura, Toshihide Ibaraki:
  An Index for the Data Size to Extract Decomposable Structures in LAD. 279-290
  

Invited Talk 2

• Michael R. Fellows:
  Parameterized Complexity: The Main Ideas and Some Research Frontiers. 291-307
  
• Therese C. Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov:
  Tight Bounds on Maximal and Maximum Matchings. 308-319
  

Graph Drawing and Algorithms (II)

• Stavros D. Nikolopoulos, Leonidas Palios:
  Recognition and Orientation Algorithms for P₄-Comparability Graphs. 320-331
  
• Danny Z. Chen, Xiaodong Wu:
  Efficient Algorithms for k-Terminal Cuts on Planar Graphs. 332-344
  
• Anna Galluccio, Guido Proietti:
  Polynomial Time Algorithms for Edge-Connectivity Augmentation of Hamiltonian Paths. 345-354
  

Combinatorial Generation and Optimization (II)

• Michael H. Albert, Robert E. L. Aldred, Mike D. Atkinson, Derek A. Holton:
  Algorithms for Pattern Involvement in Permutations. 355-366
  
• Takeaki Uno:
  A Fast Algorithm for Enumerating Bipartite Perfect Matchings. 367-379
  
• Bo Chen, Xiaotie Deng, Wenan Zang:
  On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time. 380-389
  
• Thomas Erlebach, Martin Gantenbein, Daniel Hürlimann, Gabriele Neyer, Aris Pagourtzis, Paolo Penna, Konrad Schlude, Kathleen Steinhöfel, David Scot Taylor, Peter Widmayer:
  On the Complexity of Train Assignment Problems. 390-402
  

Computational Biology and String Matching (I)

• James Aspnes, Julia Hartling, Ming-Yang Kao, Junhyong Kim, Gauri Shah:
  A Combinatorial Toolbox for Protein Sequence Design and Landscape Analysis in the Grand Canonical Model. 403-415
  
• Rune B. Lyngsø, Christian N. S. Pedersen:
  Complexity of Comparing Hidden Markov Models. 416-428
  
• Ming-Yang Kao, Vijay Ramachandran:
  DNA Self-Assembly For Constructing 3D Boxes. 429-440
  
• Jens Gramm, Rolf Niedermeier, Peter Rossmanith:
  Exact Solutions for CLOSEST STRING and Related Problems. 441-453
  

Computational Geometry (II)

• Danny Z. Chen, Shuang Luan, Jinhui Xu:
  Topological Peeling and Implementation. 454-466
  
• Danny Z. Chen, Jie Wang, Xiaodong Wu:
  Image Segmentation with Monotonicity and Smoothness Constraints. 467-479
  
• Jae-Ha Lee, Sang-Min Park, Kyung-Yong Chwa:
  Optimization Algorithms for Sweeping a Polygonal Region with Mobile Guards. 480-492
  
• Sofia Kovaleva, Frits C. R. Spieksma:
  Approximation of a Geometric Set Covering Problem. 493-501
  

Invited Talk 3

• Andrew V. Goldberg:
  Shortest Path Algorithms: Engineering Aspects. 502-513
  

Graph Drawing and Algorithms (III)

• Xiao Zhou, Takao Nishizeki:
  Efficient Algorithms for Weighted Colorings of Series-Parallel Graphs. 514-524
  
• Marcus Peinado:
  Go with the Winners Algorithms for Cliques in Random Graphs. 525-536
  
• Jirí Fiala, Jan Kratochvíl:
  Complexity of Partial Covers of Graphs. 537-549
  
• Hans L. Bodlaender, Michael J. Dinneen, Bakhadyr Khoussainov:
  On Game-Theoretic Models of Networks. 550-561
  

Parallel and Distributed Algorithms (II)

• Andreas Jakoby, Maciej Liskiewicz:
  The Complexity of Some Basic Problems for Dynamic Process Graphs. 562-574
  
• Xuemin Lin:
  Delay Optimizations in Quorum Consensus. 575-586
  
• Hyunyoung Lee, Jennifer L. Welch:
  Randomized Shared Queues Applied to Distributed Optimization Algorithms. 587-598
  
• Andrej Brodnik, Johan Karlsson:
  Multiprocess Time Queue. 599-609
  

Computational Geometry (III)

• Sheung-Hung Poon, Chan-Su Shin, Tycho Strijk, Alexander Wolff:
  Labeling Points with Weights. 610-622
  
• David Bremner, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristan:
  Small Convex Quadrangulations of Point Sets. 623-635
  
• Tetsuo Asano, Takeshi Tokuyama:
  How to Color a Checkerboard with a Given Distribution - Matrix Rounding Achieving Low 2×2-Discrepancy. 636-648
  
• Maria Angeles Garrido, Claudia Iturriaga, Alberto Márquez, José Ramón Portillo, Pedro Reyes, Alexander Wolff:
  Labeling Subway Lines. 649-659
  

Randomized and Approximation Algorithms

• Louxin Zhang, Song Zhu:
  Complexity Study on Two Clustering Problems. 660-669
  
• Toshihiro Fujito, Tsuyoshi Okumura:
  A Modified Greedy Algorithm for the Set Cover Problem with Weights 1 and 2. 670-681
  
• Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki:
  A Unified Framework for Approximating Multiway Partition Problems. 682-694
  
• Luitpold Babel, Bo Chen, Hans Kellerer, Vladimir Kotov:
  On-Line Algorithms for Cardinality Constrained Bin Packing Problems. 695-706
  

Computational Biology and String Matching (II)

• Krisztián Monostori, Arkady B. Zaslavsky, István Vajk:
  Suffix Vector: A Space-Efficient Suffix Tree Representation. 707-718
  
• Hideaki Hori, Shinichi Shimozono, Masayuki Takeda, Ayumi Shinohara:
  Fragmentary Pattern Matching: Complexity, Algorithms and Applications for Analyzing Classic Literary Works. 719-730
  
• Gerth Stølting Brodal, Rolf Fagerberg, Christian N. S. Pedersen:
  Computing the Quartet Distance between Evolutionary Trees in Time O(n log² n). 731-742
  

Algorithms and Data Structures

• Ronald I. Becker, Yen-I Chiang, Isabella Lari, Andrea Scozzari:
  The Cent-dian Path Problem on Tree Networks. 743-755
  
• Evangelos Kranakis, Danny Krizanc, Sunil M. Shende:
  Approximate Hotlink Assignment. 756-767
  
• Shan-Chyun Ku, Chi-Jen Lu, Biing-Feng Wang, Tzu-Chin Lin:
  Efficient Algorithms for Two Generalized 2-Median Problems on Trees. 768-778