15. COCOON 2009: Niagara Falls, NY, USA

Hung Q. Ngo (Ed.): Computing and Combinatorics, 15th Annual International Conference, COCOON 2009, Niagara Falls, NY, USA, July 13-15, 2009, Proceedings. Lecture Notes in Computer Science 5609 Springer 2009, ISBN 978-3-642-02881-6

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