Computing and Combinatorics

1. Front Matter

   PDF

2. Invited Presentations

   1. External Geometric Data Structures

      • Lars Arge

      Pages 1-1

   2. The Poisson Cloning Model for Random Graphs, Random Directed Graphs and Random k-SAT Problems

      • Jeong Han Kim

      Pages 2-2

   3. Robust Geometric Computation Based on Digital Topology

      • Kokichi Sugihara

      Pages 3-12

3. Data Structures and Algorithms I

   1. Adjacency of Optimal Regions for Huffman Trees

      • Kensuke Onishi

      Pages 13-22

   2. A Construction Method for Optimally Universal Hash Families and Its Consequences for the Existence of RBIBDs

      • Philipp Woelfel

      Pages 23-32

   3. Towards Constructing Optimal Strip Move Sequences

      • Meena Mahajan, Raghavan Rama, S. Vijayakumar

      Pages 33-42

4. Computational Geometry I

   1. Large Triangles in the d-Dimensional Unit-Cube

      • Hanno Lefmann

      Pages 43-52

   2. Progress on Maximum Weight Triangulation

      • Francis Y. L. Chin, Jianbo Qian, Cao An Wang

      Pages 53-61

   3. Coloring Octrees

      • Udo Adamy, Michael Hoffmann, József Solymosi, Miloš Stojaković

      Pages 62-71

5. Games and Combinatorics

   1. Some Open Problems in Decidability of Brick (Labelled Polyomino) Codes

      • Małgorzata Moczurad, Włodzimierz Moczurad

      Pages 72-81

   2. Q-Ary Ulam-Rényi Game with Weighted Constrained Lies

      • Ferdinando Cicalese, Christian Deppe, Daniele Mundici

      Pages 82-91

   3. Necessary and Sufficient Numbers of Cards for the Transformation Protocol

      • Koichi Koizumi, Takaaki Mizuki, Takao Nishizeki

      Pages 92-101

6. Combinatorial Optimization I

   1. On the Selection and Assignment with Minimum Quantity Commitments

      • Andrew Lim, Fan Wang, Zhou Xu

      Pages 102-111

   2. Approximation Algorithms for Multicommodity Flow and Normalized Cut Problems: Implementations and Experimental Study

      • Ying Du, Danny Z. Chen, Xiaodong Wu

      Pages 112-121

   3. Transshipment Through Crossdocks with Inventory and Time Windows

      • Andrew Lim, Zhaowei Miao, Brian Rodrigues, Zhou Xu

      Pages 122-131

7. Graph Algorithms

   1. Approximated Vertex Cover for Graphs with Perfect Matchings

      • Tomokazu Imamura, Kazuo Iwama, Tatsuie Tsukiji

      Pages 132-142

   2. An Approximation Algorithm for Weighted Weak Vertex Cover Problem in Undirected Graphs

      • Yong Zhang, Hong Zhu

      Pages 143-150

   3. On the Arrangement of Cliques in Chordal Graphs with Respect to the Cuts

      • L. Sunil Chandran, N. S. Narayanaswamy

      Pages 151-160

   4. The Worst-Case Time Complexity for Generating All Maximal Cliques

      • Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi

      Pages 161-170

Thepapersinthisvolumewereselectedforpresentationatthe10thInternational Computing and Combinatorics Conference (COCOON 2004), held on August 17–20, 2004 in Jeju Island, Korea. Previous meetings were held in Xi’an (1995), HongKong(1996),Shanghai(1997),Taipei(1998),Tokyo(1999),Sydney(2000), Guilin (2001), Singapore (2002), and Big Sky (2003). In response to the call for papers, 109 extended abstracts were submitted from 23 countries, of which 46 were accepted. The submitted papers were from Belgium (1), Canada (5), China (6), France (1), Germany (6), Hong Kong (8), India (6), Iran (1), Ireland (1), Israel (4), Italy (2), Japan (17), Korea (23), Mexico (3), New Zealand (1), Poland(1), Russia (1), Singapore (5), Sweden (2), Switzerland (3), Taiwan (2), the UK (1), and the USA (9). Each paper was evaluated by at least three program committee members, with the assistance of referees, as indicated by the referee list found in these proceedings. There were many more acceptable papers than there was space available in the conference schedule, and the program committee’s task was extremely di?cult. In addition to selected papers, the conference also included threeinvitedpresentationsbyLarsArge,JeongHanKim,andKokichiSugihara. We thank all program committee members and their referees for their - cellent work, especially given the demanding time constraints; they gave the conference its distinctive character. We thank all who submitted papers for c- sideration: they all contributed to the high quality of the conference. Finally,wethankallthepeoplewhoworkedhardtoputinplacethelogistical arrangements of the conference — our colleagues and our graduate students. It is their hard work that made the conference possible and enjoyable.

• Automat
• algorithms
• automata
• combinatorial optimization
• complexity
• complexity theory
• computational geometry
• data structures
• optimization
• algorithm analysis and problem complexity

• Division of Computer Science, Korea Advanced Institute of Science and Technology, Daejeon, Republic of Korea

  Kyung-Yong Chwa

• Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada

  J. Ian J. Munro

Policies and ethics