5. COCOON 1999: Tokyo, Japan

@proceedings{DBLP:conf/cocoon/99,
  editor    = {Takao Asano and
               Hiroshi Imai and
               D. T. Lee and
               Shin-Ichi Nakano and
               Takeshi Tokuyama},
  title     = {Computing and Combinatorics, 5th Annual International Conference,
               COCOON '99, Tokyo, Japan, July 26-28, 1999, Proceedings},
  booktitle = {COCOON},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1627},
  year      = {1999},
  isbn      = {3-540-66200-6},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Talks

• Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins:
  The Web as a Graph: Measurements, Models, and Methods. 1-17
  
• Jun Tarui, Seinosuke Toda:
  Some Observations on the Computational Complexity of Graph Accessibility Problem. 18-30
  

Hao Wang Award Paper

• Hiroshi Nagamochi, Toshihide Ibaraki:
  An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree. 31-40
  

Data Structures

• Tadao Takaoka:
  Theory of 2-3 Heaps. 41-50
  
• David A. Hutchinson, Anil Maheshwari, Norbert Zeh:
  An External Memory Data Structure for Shortest Path Queries. 51-60
  

Computational Biology

• Wing-Kai Hon, Tak Wah Lam:
  Approximating the Nearest Neighbor Interchange Distance for Evolutionary Trees with Non-uniform Degrees. 61-70
  
• Guo-Hui Lin, Guoliang Xue:
  Signed Genome Rearrangement by Reversals and Transpositions: Models and Approximations. 71-80
  

Graph Drawing

• Atsuko Yamaguchi, Akihiro Sugimoto:
  An Approximation Algorithm for the Two-Layered Graph Drawing Problem. 81-91
  
• Xuemin Lin, Peter Eades:
  Area Minimization for Grid Visibility Representation of Hierarchically Planar Graphs. 92-102
  
• Josep Díaz, Mathew D. Penrose, Jordi Petit, Maria J. Serna:
  Layout Problems on Lattice Graphs. 103-112
  

Discrete Mathematics

• Jin-yi Cai:
  A New Transference Theorem in the Geometry of Numbers. 113-122
  
• Carsten Damm, Ki Hang Kim, Fred W. Roush:
  On Covering and Rank Problems for Boolean Matrices and Their Applications. 123-133
  
• Meena Mahajan, P. R. Subramanya, V. Vinay:
  A Combinatorial Algorithm for Pfaffians. 134-143
  

Graph Algorithms 1

• Enrico Nardelli, Guido Proietti, Peter Widmayer:
  How to Swap a Failing Edge of a Single Source Shortest Paths Tree. 144-153
  
• Sergei L. Bezrukov, Robert Elsässer, Ulf-Peter Schroeder:
  On Bounds for the k-Partitioning of Graphs. 154-163
  
• Hiroshi Nagamochi, Shigeki Katayama, Toshihide Ibaraki:
  A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs. 164-173
  

Automata and Language

• Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Arnolds Kikusts:
  Probabilities to Accept Languages by Quantum Finite Automata. 174-183
  
• Lance Fortnow, Aduri Pavan, Alan L. Selman:
  Distributionally-Hard Languages. 184-193
  
• Pierre McKenzie, Klaus Reinhardt, V. Vinay:
  Circuits and Context-Free Languages. 194-203
  

Complexity Theory and Learning

• Kazuyuki Amano, Akira Maruoka, Jun Tarui:
  On the Negation-Limited Circuit Complexity of Merging. 204-209
  
• Peter Bro Miltersen, N. V. Vinodchandran, Osamu Watanabe:
  Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy. 210-220
  
• Henning Fernau:
  Efficient Learning of Some Linear Matrix Languages. 221-230
  

Combinatorial Optimization 1

• Xiaotie Deng, Yuzhong Zhang:
  Minimizing Mean Response Time in Batch Processing System. 231-240
  
• Piotr Krysta, Roberto Solis-Oba:
  Approximation Algorithms for Bounded Facility Location. 241-250
  
• Satoshi Tayu:
  Scheduling Trees onto Hypercubes and Grids Is NP-complete. 251-260
  

Graph Algorithms 2

• Magnús M. Halldórsson:
  Approximations of Weighted Independent Set and Hereditary Subset Problems. 261-270
  
• Magnús M. Halldórsson, Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, Jan Arne Telle:
  Multi-coloring Trees. 271-280
  
• Andrea E. F. Clementi, Pierluigi Crescenzi, Gianluca Rossi:
  On the Complexity of Approximating Colored-Graph Problems. 281-290
  

Number Theory

• Anna Bernasconi, Carsten Damm, Igor Shparlinski:
  On the Average Sensitivity of Testing Square-Free Numbers. 291-299
  
• Xizhong Zheng:
  Binary Enumerability of Real Numbers. 300-309
  
• Gene Cooperman, Sandra Feisel, Joachim von zur Gathen, George Havas:
  GCD of Many Integers. 310-317
  

Distributed Computing

• Tomasz Jurdzinski, Miroslaw Kutylowski, Krzysztof Lorys:
  Multi-party Finite Computations. 318-329
  
• Toshio Nakata, Hiroshi Imahayashi, Masafumi Yamashita:
  Probabilistic Local Majority Voting for the Agreement Problem on Finite Graphs. 330-338
  

Combinatorial Optimization 2

• Ambros Marzetta, Adrian Brüngger:
  A Dynamic-Programming Bound for the Quadratic Assignment Problem. 339-348
  
• Takeaki Uno:
  A New Approach for Speeding Up Enumeration Algorithms and Its Application for Matroid Bases. 349-359
  

Network Routing Problems

• Jin-yi Cai, George Havas, Bernard Mans, Ajay Nerurkar, Jean-Pierre Seifert, Igor Shparlinski:
  On Routing in Circulant Graphs. 360-369
  
• Akira Matsubayashi, Ryo Takasu:
  Minimum Congestion Embedding of Complete Binary Trees into Tori. 370-378
  

Computational Geometry

• Francis Y. L. Chin, Cao An Wang, Fu Lee Wang:
  Maximum Stabbing Line in 2D Plane. 379-388
  
• Jeet Chaudhuri, Subhas C. Nandy:
  Generalized Shooter Location Problem. 389-399
  

Online Algorithms

• Sung-Pil Hong:
  A Competitive Online Algorithm for the Paging Problem with "Shelf" Memory. 400-408
  
• Kazuo Iwama, Kouki Yonezawa:
  Using Generalized Forecasts for Online Currency Conversion. 409-421
  

Rewriting Systems

• Friedrich Otto:
  On S-Regular Prefix-Rewriting Systems and Automatic Structures. 422-431
  
• Kouichi Hirata, Keizo Yamada, Masateru Harao:
  Tractable and Intractable Second-Order Matching Problems. 432-441
  

Parallel Computing

• Sung-Woo Lee, Hyun-Sung Kim, Jung-Joon Kim, Tae-Geun Kim, Kee-Young Yoo:
  Efficient Fixed-Size Systolic Arrays for the Modular Multiplication. 442-451
  
• Ka Wong Chong, Yijie Han, Yoshihide Igarashi, Tak Wah Lam:
  Improving Parallel Computation with Fast Integer Sorting. 452-461
  
• Sajal K. Das, Bhabani P. Sinha, Rajarshi Chaudhuri:
  A Cominatorial Approach to Performance Analysis of a Shared-Memory Multiprocessor. 462-472
  

Combinatorial Optimization 3

• Joachim Gudmundsson, Christos Levcopoulos:
  A Fast Approximation Algorithm for TSP with Neighborhoods and Red-Blue Separation. 473-482
  
• H. Y. Lau, H. F. Ting:
  The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set. 483-492