10. COCOON 2004: Jeju Island, Korea

Invited Presentations

• Lars Arge:
  External Geometric Data Structures. 1
  
• Jeong Han Kim:
  The Poisson Cloning Model for Random Graphs, Random Directed Graphs and Random k-SAT Problems. 2
  
• Kokichi Sugihara:
  Robust Geometric Computation Based on Digital Topology. 3-12
  

Data Structures and Algorithms I

• Kensuke Onishi:
  Adjacency of Optimal Regions for Huffman Trees. 13-22
  
• Philipp Woelfel:
  A Construction Method for Optimally Universal Hash Families and Its Consequences for the Existence of RBIBDs. 23-32
  
• Meena Mahajan, Raghavan Rama, S. Vijayakumar:
  Towards Constructing Optimal Strip Move Sequences. 33-42
  

Computational Geometry I

• Hanno Lefmann:
  Large Triangles in the d-Dimensional Unit-Cube. 43-52
  
• Francis Y. L. Chin, Jianbo Qian, Cao An Wang:
  Progress on Maximum Weight Triangulation. 53-61
  
• Udo Adamy, Michael Hoffmann, József Solymosi, Milos Stojakovic:
  Coloring Octrees. 62-71
  

Games and Combinatorics

• Malgorzata Moczurad, Wlodzimierz Moczurad:
  Some Open Problems in Decidability of Brick (Labelled Polyomino) Codes. 72-81
  
• Ferdinando Cicalese, Christian Deppe, Daniele Mundici:
  Q-Ary Ulam-Rényi Game with Weighted Constrained Lies. 82-91
  
• Koichi Koizumi, Takaaki Mizuki, Takao Nishizeki:
  Necessary and Sufficient Numbers of Cards for the Transformation Protocol. 92-101
  

Combinatorial Optimization I

• Andrew Lim, Fan Wang, Zhou Xu:
  On the Selection and Assignment with Minimum Quantity Commitments. 102-111
  
• Ying Du, Danny Z. Chen, Xiaodong Wu:
  Approximation Algorithms for Multicommodity Flow and Normalized Cut Problems: Implementations and Experimental Study. 112-121
  
• Andrew Lim, Zhaowei Miao, Brian Rodrigues, Zhou Xu:
  Transshipment Through Crossdocks with Inventory and Time Windows. 122-131
  

Graph Algorithms

• Tomokazu Imamura, Kazuo Iwama, Tatsuie Tsukiji:
  Approximated Vertex Cover for Graphs with Perfect Matchings. 132-142
  
• Yong Zhang, Hong Zhu:
  An Approximation Algorithm for Weighted Weak Vertex Cover Problem in Undirected Graphs. 143-150
  
• L. Sunil Chandran, N. S. Narayanaswamy:
  On the Arrangement of Cliques in Chordal Graphs with Respect to the Cuts. 151-160
  
• Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi:
  The Worst-Case Time Complexity for Generating All Maximal Cliques. 161-170
  

Automata and Learning Theory

• Michael Kaminski, Tony Tan:
  Regular Expressions for Languages over Infinite Alphabets. 171-178
  
• Masaki Nakanishi:
  On the Power of One-Sided Error Quantum Pushdown Automata with Classical Stack Operations. 179-186
  
• N. V. Vinodchandran:
  Learning DNFs and Circuits Using Teaching Assistants. 188-197
  
• Joel Ratsaby:
  On the Complexity of Samples for Learning. 198-209
  

Scheduling

• Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, Prudence W. H. Wong:
  New Results on On-Demand Broadcasting with Deadline via Job Scheduling with Cancellation. 210-218
  
• Fabien Baille, Evripidis Bampis, Christian Laforest:
  Maximization of the Size and the Weight of Schedules of Degradable Intervals. 219-228
  
• Shuguang Li, Guojun Li, Shaoqiang Zhang:
  Minimizing Maximum Lateness on Identical Parallel Batch Processing Machines. 229-237
  

Computational Geometry II

• Danny Z. Chen, Jinhee Chun, Naoki Katoh, Takeshi Tokuyama:
  Efficient Algorithms for Approximating a Multi-dimensional Voxel Terrain by a Unimodal Terrain. 238-248
  
• Tatsuya Akutsu:
  Algorithms for Point Set Matching with k-Differences. 249-258
  
• Hee-Kap Ahn, Peter Braß, Otfried Cheong, Hyeon-Suk Na, Chan-Su Shin, Antoine Vigneron:
  Approximation Algorithms for Inscribing or Circumscribing an Axially Symmetric Polygon to a Convex Polygon. 259-267
  

Data Structures and Algorithms II

• Vladimir G. Deineko, Michael Hoffmann, Yoshio Okamoto, Gerhard J. Woeginger:
  The Traveling Salesman Problem with Few Inner Points. 268-277
  
• Tadao Takaoka:
  A Faster Algorithm for the All-Pairs Shortest Path Problem and Its Application. 278-289
  
• Giorgio Ausiello, Marc Demange, Luigi Laura, Vangelis Th. Paschos:
  Algorithms for the On-Line Quota Traveling Salesman Problem. 290-299
  

Graph Drawing

• Kumiko Nomura, Satoshi Tayu, Shuichi Ueno:
  On the Orthogonal Drawing of Outerplanar Graphs. 300-308
  
• Kazuyuki Miura, Machiko Azuma, Takao Nishizeki:
  Canonical Decomposition, Realizer, Schnyder Labeling and Orderly Spanning Trees of Plane Graphs. 309-318
  
• Zhi-Zhong Chen:
  New Bounds on the Number of Edges in a k-Map Graph. 319-328
  

Combinatorial Optimization II

• N. S. Narayanaswamy:
  Dynamic Storage Allocation and On-Line Colouring Interval Graphs. 329-338
  
• Shuai Cheng Li, Hon Wai Leong, Steven K. Quek:
  New Approximation Algorithms for Some Dynamic Storage Allocation Problems. 339-348
  
• Andrew Lim, Brian Rodrigues, Fan Wang, Zhou Xu:
  k-Center Problems with Minimum Coverage. 349-359
  

Complexity Theory

• Xizhong Zheng, Robert Rettinger:
  On the Extensions of Solovay-Reducibility.. 360-369
  
• Gustav Nordh, Peter Jonsson:
  The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups. 370-379
  
• Narayan Vikas:
  Computational Complexity Classification of Partition under Compaction and Retraction. 380-391
  

Parallel and Distributed Architectures

• Jung-Heum Park:
  One-to-Many Disjoint Path Covers in a Graph with Faulty Elements. 392-401
  
• Toshinori Yamada:
  Fault-Tolerant Meshes with Constant Degree. 402-411
  
• Kyoung-Wook Park, Hyeong-Seok Lim, Jung-Heum Park, Hee-Chul Kim:
  Fault Hamiltonicity of Meshes with Two Wraparound Edges. 412-421
  
• Toshio Nakata:
  On the Expected Time for Herman's Probabilistic Self-stabilizing Algorithm. 422-431
  

Computational Biology

• Ho-fung Leung, Zeshan Peng, Hing-Fung Ting:
  An Efficient Online Algorithm for Square Detection. 432-439
  
• Jin Wook Kim, Kunsoo Park:
  An Efficient Local Alignment Algorithm for Masked Sequences. 440-449
  
• Tatsuie Tsukiji, Zhi-Zhong Chen:
  Computing Phylogenetic Roots with Bounded Degrees and Errors Is Hard. 450-461
  
• Jesper Jansson, Wing-Kin Sung:
  Inferring a Level-1 Phylogenetic Network from a Dense Set of Rooted Triplets. 462-472