10. COCOON 2004: Jeju Island, Korea

Kyung-Yong Chwa, J. Ian Munro (Eds.): Computing and Combinatorics, 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004, Proceedings. Lecture Notes in Computer Science 3106 Springer 2004, ISBN 3-540-22856-X BibTeX

Invited Presentations

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

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

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

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

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

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

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
Electronic Edition (link) BibTeX
Fabien Baille, Evripidis Bampis, Christian Laforest:
Maximization of the Size and the Weight of Schedules of Degradable Intervals. 219-228
Electronic Edition (link) BibTeX
Shuguang Li, Guojun Li, Shaoqiang Zhang:
Minimizing Maximum Lateness on Identical Parallel Batch Processing Machines. 229-237
Electronic Edition (link) BibTeX

Danny Z. Chen, Jinhee Chun, Naoki Katoh, Takeshi Tokuyama:
Efficient Algorithms for Approximating a Multi-dimensional Voxel Terrain by a Unimodal Terrain. 238-248
Electronic Edition (link) BibTeX
Tatsuya Akutsu:
Algorithms for Point Set Matching with k-Differences. 249-258
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX

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

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

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

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

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

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