Computing and Combinatorics: 15th Annual International Conference, COCOON 2009 Niagara Falls, NY, USA, July 13-15, 2009 Proceedings

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 -