9. COCOON 2003: Big Sky, MT, USA

Invited Lecture

• Joel Spencer:
  LIAR! 1-2
  
• Jon Louis Bentley:
  Experiments for Algorithm Engineering. 3-4
  
• Ren Hua Chung, Dan Gusfield:
  Empirical Exploration of Perfect Phylogeny Haplotyping and Haplotypers. 5-19
  

Computational Geometry I

• Sergei Bespamyatnikh:
  Cylindrical Hierarchy for Deforming Necklaces. 20-29
  
• Danny Z. Chen, Bin Xu:
  Geometric Algorithms for Agglomerative Hierarchical Clustering. 30-39
  
• Jinhui Xu, Yang Yang, Zhiyong Lin:
  Traveling Salesman Problem of Segments. 40-49
  
• Andrzej Lingas, Martin Wahlen:
  Subexponential-Time Algorithms for Maximum Independent Set and Related Problems on Box Graphs. 50-56
  

Computational Biology I

• Yong Gao, Junfeng Wu, Robert Niewiadomski, Yang Wang, Zhi-Zhong Chen, Guohui Lin:
  A Space Efficient Algorithm for Sequence Alignment with Inversions. 57-67
  
• Anne Bergeron, Jens Stoye:
  On the Similarity of Sets of Permutations and Its Applications to Genome Comparison. 68-79
  
• Wei Fu, Wing-Kai Hon, Wing-Kin Sung:
  On All-Substrings Alignment Problems. 80-89
  

Computational/Complexity Theory I

• Eldar Fischer, Johann A. Makowsky:
  The Specker-Blatter Theorem Revisited. 90-101
  
• Xizhong Zheng:
  On the Divergence Bounded Computable Real Numbers. 102-111
  
• Hanno Lefmann:
  Sparse Parity-Check Matrices over Finite Fields (Extended Abstract). 112-121
  

Graph Theory/Algorithms I

• Yen Hung Chen, Chin Lung Lu, Chuan Yi Tang:
  On the Full and Bottleneck Full Steiner Tree Problems. 122-129
  
• Tetsuo Asano, Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama:
  The Structure and Number of Global Roundings of a Graph. 130-138
  
• Huaming Zhang, Xin He:
  On Even Triangulations of 2-Connected Embedded Graphs. 139-148
  

Automata/Petri Net Theory

• Hsu-Chun Yen, Lien-Po Yu:
  Petri Nets with Simple Circuits. 149-158
  
• Pierluigi San Pietro, Zhe Dang:
  Automatic Verification of Multi-queue Discrete Timed Automata. 159-171
  

Graph Theory/Algorithms II

• Xiao Zhou, Yuki Matsuo, Takao Nishizeki:
  List Total Colorings of Series-Parallel Graphs. 172-181
  
• Therese C. Biedl, Brona Brejová, Erik D. Demaine, Angèle M. Hamel, Alejandro López-Ortiz, Tomás Vinar:
  Finding Hidden Independent Sets in Interval Graphs. 182-191
  
• Kenji Kashiwabara, Yoshio Okamoto, Takeaki Uno:
  Matroid Representation of Clique Complexes. 192-201
  

Complexity Theory II

• Jin-yi Cai, Osamu Watanabe:
  On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results. 202-211
  
• Martin Kutz:
  The Complexity of Boolean Matrix Root Computation. 212-221
  
• Hiroaki Yamamoto, Takashi Miyazaki:
  A Fast Bit-Parallel Algorithm for Matching Extended Regular Expressions. 222-231
  

Distributed Computing

• Masataka Takamura, Yoshihide Igarashi:
  Group Mutual Exclusion Algorithms Based on Ticket Orders. 232-241
  
• Andrzej Czygrinow, Michal Hanckowiak:
  Distributed Algorithm for Better Approximation of the Maximum Matching. 242-251
  
• Eric J. Schwabe, Ian M. Sutherland:
  Efficient Mappings for Parity-Declustered Data Layouts. 252-261
  

Web-Based Computing

• Xiaotie Deng, Qizhi Fang, Shanfeng Zhu:
  Approximate Rank Aggregation (Preliminary Version). 262-271
  
• Hyun Chul Lee, Allan Borodin:
  Perturbation of the Hyper-Linked Environment. 272-283
  
• Zhixiang Chen, Richard H. Fowler, Ada Wai-Chee Fu, Chunyue Wang:
  Fast Construction of Generalized Suffix Trees Over a Very Large Alphabet. 284-293
  

Complexity Theory III

• Eike Kiltz, Hans-Ulrich Simon:
  Complexity Theoretic Aspects of Some Cryptographic Functions. 294-303
  
• Kazuo Iwama, Akinori Kawachi, Shigeru Yamashita:
  Quantum Sampling for Balanced Allocations. 304-318
  

Graph Theory/Algorithms III

• Jung-Heum Park, Hee-Chul Kim:
  Fault-Hamiltonicity of Product Graph of Path and Cycle. 319-328
  
• Yosuke Kikuchi, Hiroyuki Tanaka, Shin-Ichi Nakano, Yukio Shibata:
  How to Obtain the Complete List of Caterpillars (Extended Abstract). 329-338
  
• Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa:
  Randomized Approximation of the Stable Marriage Problem. 339-350
  

Computational Geometry II

• Erik D. Demaine, Susan Hohenberger, David Liben-Nowell:
  Tetris is Hard, Even to Approximate. 351-363
  
• Xiang-Yang Li:
  Approximate MST for UDG Locally. 364-373
  
• Xiang-Yang Li, Yu Wang:
  Efficient Construction of Low Weight Bounded Degree Planar Spanner. 374-384
  

Graph Theory/Algorithms IV

• L. Sunil Chandran, Telikepalli Kavitha, C. R. Subramanian:
  Isoperimetric Inequalities and the Width Parameters of Graphs. 385-393
  
• Faisal N. Abu-Khzam, Michael A. Langston:
  Graph Coloring and the Immersion Order. 394-403
  
• Carlo Gaibisso, Guido Proietti, Richard B. Tan:
  Optimal MST Maintenance for Transient Deletion of Every Node in Planar Graphs. 404-414
  

Scheduling

• Jae-Hoon Kim, Kyung-Yong Chwa:
  Scheduling Broadcasts with Deadlines. 415-424
  
• Francis Y. L. Chin, Stanley P. Y. Fung:
  Improved Competitive Algorithms for Online Scheduling with Partial Job Values. 425-434
  
• Lihua Chen, Xiaotie Deng, Qizhi Fang, Feng Tian:
  Majority Equilibrium for Public Facility Allocation (Preliminary Version). 435-444
  

Computational Geometry III

• Günter Rote, Cao An Wang, Lusheng Wang, Yin-Feng Xu:
  On Constrained Minimum Pseudotriangulations. 445-454
  
• Xiaodong Wu, Danny Z. Chen, James J. Mason, Steven R. Schmid:
  Pairwise Data Clustering and Applications. 455-466
  
• Michael J. Collins:
  Covering a Set of Points with a Minimum Number of Turns. 467-474
  

Graph Drawing

• Ashim Garg, Adrian Rusu:
  Area-Efficient Order-Preserving Planar Straight-Line Drawings of Ordered Trees. 475-486
  
• Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrto:
  Bounds for Convex Crossing Numbers. 487-495
  
• Yehuda Koren:
  On Spectral Graph Drawing. 496-508
  

Computational Biology II

• Yih-En Andrew Ban, Sergei Bespamyatnikh, Nabil H. Mustafa:
  On a Conjecture on Wiener Indices in Combinatorial Chemistry. 509-518
  
• Mark Cieliebak, Stephan Eidenbenz, Gerhard J. Woeginger:
  Double Digest Revisited: Complexity and Approximability in the Presence of Noisy Data. 519-527
  
• Ronald I. Greenberg:
  Fast and Space-Efficient Location of Heavy or Dense Segments in Run-Length Encoded Sequences: (Extended Abstract). 528-536
  
• Mark Marron, Krister M. Swenson, Bernard M. E. Moret:
  Genomic Distances under Deletions and Insertions. 537-547
  

Fixed-Parameter Complexity Theory

• Stefan Szeider:
  Minimal Unsatisfiable Formulas with Bounded Clause-Variable Difference are Fixed-Parameter Tractable. 548-558
  

Last update Sat May 25 17:38:37 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page