5. COCOON 1999: Tokyo, Japan
- Takao Asano, Hiroshi Imai, D. T. Lee, Shin-Ichi Nakano, Takeshi Tokuyama:
Computing and Combinatorics, 5th Annual International Conference, COCOON '99, Tokyo, Japan, July 26-28, 1999, Proceedings. Lecture Notes in Computer Science 1627, Springer 1999, ISBN 3-540-66200-6
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
- 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
- Carsten Damm, Ki Hang Kim, Fred W. Roush:
On Covering and Rank Problems for Boolean Matrices and Their Applications. 123-133
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
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
Combinatorial Optimization 1
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 E. Shparlinski:
On the Average Sensitivity of Testing Square-Free Numbers. 291-299
Distributed Computing
- 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 E. 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
Online Algorithms
Rewriting Systems
- 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