This volume constitutes the refereed proceedings of the 15th International Computing and Combinatorics Conference, COCOON 2009, held in New York, NY, USA in July 2009. The 51 revised extended abstracts presented were carefully reviewed and selected from 125 submissions. The papers are organized in topical sections on algorithmic game theory and coding theory, algorithms and data structures, graph drawing, algorithms and data structures, cryptography and security, algorithms, computational geometry, approximation algorithms, computational biology and bioinformatics, sampling and learning, complexity and computability, probabilistic analysis, and algorithms and data structures.
Author(s): S. Muthukrishnan (auth.), Hung Q. Ngo (eds.)
Series: Lecture Notes in Computer Science 5609 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 540
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Computer Communication Networks; Data Structures; Algorithms; Combinatorics
Front Matter....Pages -
Bidding on Configurations in Internet Ad Auctions....Pages 1-6
An Attacker-Defender Game for Honeynets....Pages 7-16
On the Performances of Nash Equilibria in Isolation Games....Pages 17-26
Limits to List Decoding Random Codes....Pages 27-36
Algorithm for Finding k -Vertex Out-trees and Its Application to k -Internal Out-branching Problem....Pages 37-46
A (4 n − 4)-Bit Representation of a Rectangular Drawing or Floorplan....Pages 47-55
Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem....Pages 56-65
Coordinate Assignment for Cyclic Level Graphs....Pages 66-75
Crossing-Optimal Acyclic HP-Completion for Outerplanar st -Digraphs....Pages 76-85
Edge-Intersection Graphs of k -Bend Paths in Grids....Pages 86-95
Efficient Data Structures for the Orthogonal Range Successor Problem....Pages 96-105
Reconstruction of Interval Graphs....Pages 106-115
A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions....Pages 116-126
Minimal Assumptions and Round Complexity for Concurrent Zero-Knowledge in the Bare Public-Key Model....Pages 127-137
Efficient Non-interactive Range Proof....Pages 138-147
Approximation Algorithms for Key Management in Secure Multicast....Pages 148-157
On Smoothed Analysis of Quicksort and Hoare’s Find....Pages 158-167
On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis....Pages 168-177
Three New Algorithms for Regular Language Enumeration....Pages 178-191
Convex Partitions with 2-Edge Connected Dual Graphs....Pages 192-204
The Closest Pair Problem under the Hamming Metric....Pages 205-214
Space Efficient Multi-dimensional Range Reporting....Pages 215-224
Approximation Algorithms for a Network Design Problem....Pages 225-237
An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of Distinct Due Dates....Pages 238-248
On the Hardness and Approximability of Planar Biconnectivity Augmentation....Pages 249-257
Determination of Glycan Structure from Tandem Mass Spectra....Pages 258-267
On the Generalised Character Compatibility Problem for Non-branching Character Trees....Pages 268-276
Inferring Peptide Composition from Molecular Formulas....Pages 277-286
Optimal Transitions for Targeted Protein Quantification: Best Conditioned Submatrix Selection....Pages 287-296
Computing Bond Types in Molecule Graphs....Pages 297-306
On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries....Pages 307-316
Finding a Level Ideal of a Poset....Pages 317-327
A Polynomial-Time Perfect Sampler for the Q-Ising with a Vertex-Independent Noise....Pages 328-337
Extracting Computational Entropy and Learning Noisy Linear Functions....Pages 338-347
HITS Can Converge Slowly, but Not Too Slowly, in Score and Rank....Pages 348-357
Online Tree Node Assignment with Resource Augmentation....Pages 358-367
Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well....Pages 368-377
On Finding Small 2-Generating Sets....Pages 378-387
Convex Recoloring Revisited: Complexity and Exact Algorithms....Pages 388-397
Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone....Pages 398-407
Hierarchies and Characterizations of Stateless Multicounter Machines....Pages 408-417
Efficient Universal Quantum Circuits....Pages 418-428
An Improved Time-Space Lower Bound for Tautologies....Pages 429-438
Multiple Round Random Ball Placement: Power of Second Chance....Pages 439-448
The Weighted Coupon Collector’s Problem and Applications....Pages 449-458
Sublinear-Time Algorithms for Tournament Graphs....Pages 459-471
Classification of a Class of Counting Problems Using Holographic Reductions....Pages 472-485
Separating NE from Some Nonuniform Nondeterministic Complexity Classes....Pages 486-495
On the Readability of Monotone Boolean Formulae....Pages 496-505
Popular Matchings: Structure and Algorithms....Pages 506-515
Graph-Based Data Clustering with Overlaps....Pages 516-526
Directional Geometric Routing on Mobile Ad Hoc Networks....Pages 527-537
Back Matter....Pages -
