8. ISAAC 1997: Singapore

Invited Presentation

• Toshihide Ibaraki:
  Solving NP-hard Combinatorial Problems in the Practical Sense (Abstract). 1
  

Session 1

• Akira Tajima, Shinji Misono:
  Airline Crew-Scheduling Problem with Many Irregular Flights. 2-11
  
• Kazuyoshi Hidaka, Hiroyuki Okano:
  Practical Approach to a Facility Location Problem for Large-Scale Logistics. 12-21
  
• Satoshi Horie, Osamu Watanabe:
  Hard Instance Generation for SAT (Extended Abstract). 22-31
  

Session 2A

• Miroslaw Kutylowski, Rolf Wanka:
  Playing Tetris on Meshes and Multi-Dimensional SHEARSORT. 32-41
  
• Kaihiro Matsuura, Akira Nagoya:
  Formulation of the Addition-Shift-Sequence Problem and Its Complexity. 42-51
  
• Tatsuya Hayashi, Koji Nakano, Stephan Olariu:
  Weighted and Unweighted Selection Algorithms for k Sorted Sequences. 52-61
  

Session 2B

• Leqiang Bai, Hiroyuki Ebara, Hideo Nakano, Hajime Maeda:
  An Adaptive Distributed Fault-Tolerant Routing Algorithm for the Star Graph. 62-71
  
• Qian-Ping Gu, Hisao Tamaki:
  Multi-Color Routing in the Undirected Hypercube. 72-81
  
• Tzuoo-Hawn Yeh, Cheng-Ming Kuo, Chin-Laung Lei, Hsu-Chun Yen:
  Competitive Source Routing on Tori and Meshes. 82-91
  

Session 3A

• Takeaki Uno:
  Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs. 92-101
  
• Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki:
  Augmenting Edge and Vertex Connectivities Simultaneously. 102-111
  

Session 3B

• Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino:
  Two-Face Horn Extensions. 112-121
  
• Giorgio Ausiello, Paolo Giulio Franciosa, Daniele Frigioni, Roberto Giaccio:
  Decremental Maintenance of Reachability in Hypergraphs and Minimum Models of Horn Formulae. 122-131
  

Invited Presentation

• Charles E. Leiserson:
  Algorithmic Analysis of Multithreaded Algorithms (Abstract). 132
  

Best Paper Presentation

• Hisao Tamaki, Takeshi Tokuyama:
  A Characterization of Planar Graphs by Pseudo-Line Arrangements. 133-142
  

Session 4A

• Petrisor Panaite, Andrzej Pelc:
  Optimal Fault-Tolerant Broadcasting in Trees (Extended Abstract). 143-152
  
• Takao Asano, Kuniaki Hori, Takao Ono, Tomio Hirata:
  A Theoretical Framework of Hybrid Approaches to MAX SAT. 153-162
  
• Takashi Horiyama, Shuzo Yajima:
  Exponential Lower Bounds on the Size of OBDDs Representing Integer Divistion. 163-172
  

Session 4B

• Eisuke Dannoura, Kouichi Sakurai:
  On-Line Versus Off-Line in Money-Making Strategies with BROKERAGE. 173-182
  
• Xiaotie Deng, Christos H. Papadimitriou:
  Decision-Making by Hierarchies of Discordant Agents. 183-192
  
• Khanh Quoc Nguyen, Vijay Varadharajan, Yi Mu:
  A New Efficient Off-line Anonymous Cash Scheme. 193-201
  

Session 5A

• Zhi-Zhong Chen:
  Approximating Unweighted Connectivity Problems in Parallel. 202-211
  
• Chung Keung Poon, Vijaya Ramachandran:
  A Randomized Linear Work EREW PRAM Algorithm to Find a Minimum Spanning Forest. 212-222
  
• Mikhail J. Atallah:
  Efficient Parallel Algorithms for Planar st-Graphs. 223-232
  

Session 5B

• Bala Ravikumar:
  Peg-Solitaire, String Rewriting Systems and Finite Automata. 233-242
  
• Hartmut Klauck:
  On the Size of Probabilistic Formulae. 243-252
  
• Boris Ryabko, Andrei Fionov:
  Homophonic Coding with Logarithmic Memory Size. 253-262
  

Session 6A

• Rolf H. Möhring, Matthias Müller-Hannemann:
  Complexity and Modeling Aspects of Mesh Refinement into Quadrilaterals. 263-272
  
• Tsuyoshi Minakawa, Kokichi Sugihara:
  Topology Oriented vs. Exact Arithmetic - Experience in Implementing the Three-Dimensional Convex Hull Algorithm. 273-282
  

Session 6B

• Matthias Ott, Frank Stephan:
  The Complexity of Learning Branches and Strategies from Queries. 283-292
  
• Gabriele Neyer, Peter Widmayer:
  Singularities Make Spatial Join Scheduling Hard. 293-302
  

Session 7A

• Hsiao-Feng Steven Chen, D. T. Lee:
  A Faster One-Dimensional Topological Compaction Algorithm. 303-313
  
• Wun-Tat Chan, Francis Y. L. Chin:
  Algorithms for Finding Optimal Disjoint Paths Around a Rectangle. 314-323
  
• Yoshiyuki Kusakari, Takao Nishizeki:
  An Algorithm for Finding a Region with the Minimum Lotal L₁ from Prescribed Terminals. 324-333
  

Session 7B

• Penny E. Haxell, Martin Loebl:
  On Defect Sets in Bipartite Graphs (Extended Abstract). 334-343
  
• Maw-Shang Chang, Sun-Yuan Hsieh, Gen-Huey Chen:
  Dynamic Programming on Distance-Hereditary Graphs. 344-353
  
• Serafino Cicerone, Gabriele Di Stefano:
  On the Equivalence in Complexity among Basic Problems on Bipartite and Parity Graphs. 354-363
  

Session 8A

• Ming-Yang Kao, Tak Wah Lam, Wing-Kin Sung, Hing-Fung Ting:
  All-Cavity Maximum Matchings. 364-373
  
• S. V. Rao, Asish Mukhopadhyay:
  Fast Algorithms for Computing beta-Skeletons and Their Relatives. 374-383
  
• Yoshiaki Kyoda, Keiko Imai, Fumihiko Takeuchi, Akira Tajima:
  A Branch-and-Cut Approach for Minimum Weight Triangulation. 384-393
  

Session 8B

• Hans Kellerer, Ulrich Pferschy, Maria Grazia Speranza:
  An Efficient Approximation Scheme for the Subset-Sum Problem. 394-403
  
• Grammati E. Pantziou, George P. Pentaris, Paul G. Spirakis:
  Competitive Call Control in Mobile Networks. 404-413
  
• B. John Oommen, Juan Dong:
  Generalized Swap-with-Parent Schemes for Self-Organizing Sequential Linear Lists. 414-423
  

Last update Thu May 23 01:52:27 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page