15. COCOON 2009: Niagara Falls, NY, USA

Invited Talk

• S. Muthukrishnan:
  Bidding on Configurations in Internet Ad Auctions. 1-6
  

Algorithmic Game Theory and Coding Theory

• Jin-yi Cai, Vinod Yegneswaran, Chris Alfeld, Paul Barford:
  An Attacker-Defender Game for Honeynets. 7-16
  
• Vittorio Bilò, Michele Flammini, Gianpiero Monaco, Luca Moscardelli:
  On the Performances of Nash Equilibria in Isolation Games. 17-26
  
• Atri Rudra:
  Limits to List Decoding Random Codes. 27-36
  

Algorithms and Data Structures

• Nathann Cohen, Fedor V. Fomin, Gregory Gutin, Eun Jung Kim, Saket Saurabh, Anders Yeo:
  Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem. 37-46
  
• Toshihiko Takahashi, Ryo Fujimaki, Youhei Inoue:
  A (4n - 4)-Bit Representation of a Rectangular Drawing or Floorplan. 47-55
  
• Tomoko Izumi, Taisuke Izumi, Hirotaka Ono, Koichi Wada:
  Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem. 56-65
  

Graph Drawing

• Christian Bachmaier, Franz-Josef Brandenburg, Wolfgang Brunner, Raymund Fülöp:
  Coordinate Assignment for Cyclic Level Graphs. 66-75
  
• Tamara Mchedlidze, Antonios Symvonis:
  Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs. 76-85
  
• Therese C. Biedl, Michal Stern:
  Edge-Intersection Graphs of k-Bend Paths in Grids. 86-95
  

Algorithms and Data Structures

• Chih-Chiang Yu, Wing-Kai Hon, Biing-Feng Wang:
  Efficient Data Structures for the Orthogonal Range Successor Problem. 96-105
  
• Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara:
  Reconstruction of Interval Graphs. 106-115
  
• Akiyoshi Shioura, Mutsunori Yagiura:
  A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions. 116-126
  

Cryptography and Security

• Giovanni Di Crescenzo:
  Minimal Assumptions and Round Complexity for Concurrent Zero-Knowledge in the Bare Public-Key Model. 127-137
  
• Tsz Hon Yuen, Qiong Huang, Yi Mu, Willy Susilo, Duncan S. Wong, Guomin Yang:
  Efficient Non-interactive Range Proof. 138-147
  
• Agnes Hui Chan, Rajmohan Rajaraman, Zhifeng Sun, Feng Zhu:
  Approximation Algorithms for Key Management in Secure Multicast. 148-157
  

Algorithms

• Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi:
  On Smoothed Analysis of Quicksort and Hoare's Find. 158-167
  
• Axel Simroth, Alexander Souza:
  On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis. 168-177
  
• Margareta Ackerman, Erkki Mäkinen:
  Three New Algorithms for Regular Language Enumeration. 178-191
  

Computational Geometry

• Marwan Al-Jubeh, Michael Hoffmann, Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóth:
  Convex Partitions with 2-Edge Connected Dual Graphs. 192-204
  
• Kerui Min, Ming-Yang Kao, Hong Zhu:
  The Closest Pair Problem under the Hamming Metric. 205-214
  
• Marek Karpinski, Yakov Nekrich:
  Space Efficient Multi-dimensional Range Reporting. 215-224
  

Approximation Algorithms

• Binay K. Bhattacharya, Yuzhuang Hu, Qiaosheng Shi:
  Approximation Algorithms for a Network Design Problem. 225-237
  
• George Karakostas, Stavros G. Kolliopoulos, Jing Wang:
  An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates. 238-248
  
• Carsten Gutwenger, Petra Mutzel, Bernd Zey:
  On the Hardness and Approximability of Planar Biconnectivity Augmentation. 249-257
  

Computational Biology and Bioinformatics

• Sebastian Böcker, Birte Kehr, Florian Rasche:
  Determination of Glycan Structure from Tandem Mass Spectra. 258-267
  
• Ján Manuch, Murray Patterson, Arvind Gupta:
  On the Generalised Character Compatibility Problem for Non-branching Character Trees. 268-276
  
• Sebastian Böcker, Anton Pervukhin:
  Inferring Peptide Composition from Molecular Formulas. 277-286
  
• Rastislav Srámek, Bernd Fischer, Elias Vicari, Peter Widmayer:
  Optimal Transitions for Targeted Protein Quantification: Best Conditioned Submatrix Selection. 287-296
  
• Sebastian Böcker, Quang Bao Anh Bui, Patrick Seeber, Anke Truß:
  Computing Bond Types in Molecule Graphs. 297-306
  

Sampling and Learning

• Ivona Bezáková, Nayantara Bhatnagar, Dana Randall:
  On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries. 307-316
  
• Shuji Kijima, Toshio Nemoto:
  Finding a Level Ideal of a Poset. 317-327
  
• Masaki Yamamoto, Shuji Kijima, Yasuko Matsui:
  A Polynomial-Time Perfect Sampler for the Q-Ising with a Vertex-Independent Noise. 328-337
  
• Chia-Jung Lee, Chi-Jen Lu, Shi-Chun Tsai:
  Extracting Computational Entropy and Learning Noisy Linear Functions. 338-347
  
• Enoch Peserico, Luca Pretto:
  HITS Can Converge Slowly, but Not Too Slowly, in Score and Rank. 348-357
  

Algorithms

• Joseph Wun-Tat Chan, Francis Y. L. Chin, Hing-Fung Ting, Yong Zhang:
  Online Tree Node Assignment with Resource Augmentation. 358-367
  
• Kenneth A. Berman, Chad Yoshikawa:
  Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well. 368-377
  
• Isabelle Fagnot, Guillaume Fertin, Stéphane Vialette:
  On Finding Small 2-Generating Sets. 378-387
  
• Iyad A. Kanj, Dieter Kratsch:
  Convex Recoloring Revisited: Complexity and Exact Algorithms. 388-397
  
• Pinar Heggernes, Federico Mancini, Charis Papadopoulos, R. Sritharan:
  Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone. 398-407
  

Complexity and Computability

• Oscar H. Ibarra, Ömer Egecioglu:
  Hierarchies and Characterizations of Stateless Multicounter Machines. 408-417
  
• Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer:
  Efficient Universal Quantum Circuits. 418-428
  
• Scott Diehl, Dieter van Melkebeek, Ryan Williams:
  An Improved Time-Space Lower Bound for Tautologies. 429-438
  

Probabilistic Analysis

• Xiang-Yang Li, Yajun Wang, Wangsen Feng:
  Multiple Round Random Ball Placement: Power of Second Chance. 439-448
  
• Petra Berenbrink, Thomas Sauerwald:
  The Weighted Coupon Collector's Problem and Applications. 449-458
  
• Stefan S. Dantchev, Tom Friedetzky, Lars Nagel:
  Sublinear-Time Algorithms for Tournament Graphs. 459-471
  

Complexity and Computability

• Michael Kowalczyk:
  Classification of a Class of Counting Problems Using Holographic Reductions. 472-485
  
• Bin Fu, Angsheng Li, Liyu Zhang:
  Separating NE from Some Nonuniform Nondeterministic Complexity Classes. 486-495
  
• Khaled M. Elbassioni, Kazuhisa Makino, Imran Rauf:
  On the Readability of Monotone Boolean Formulae. 496-505
  

Algorithms and Data Structures

• Eric McDermid, Robert W. Irving:
  Popular Matchings: Structure and Algorithms. 506-515
  
• Michael R. Fellows, Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann:
  Graph-Based Data Clustering with Overlaps. 516-526
  
• Kazushige Sato, Takeshi Tokuyama:
  Directional Geometric Routing on Mobile Ad Hoc Networks. 527-537