Computing and combinatorics

InhaltsverzeichnisInvited Talk.Bidding on Configurations in Internet Ad Auctions.Algorithmic Game Theory and Coding Theory.An Attacker-Defender Game for Honeynets.On the Performances of Nash Equilibria in Isolation Games.Limits to List Decoding Random Codes.Algorithms and Data Structures.Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem.A (4n???4)-Bit Representation of a Rectangular Drawing or Floorplan.Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem.GraphDrawing.Coordinate Assignment for Cyclic Level Graphs.Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs.Edge-Intersection Graphs of k-Bend Paths in Grids.Efficient Data Structures for the Orthogonal Range Successor Problem.Reconstruction of Interval Graphs.A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions.Cryptography and Security.Minimal Assumptions and Round Complexity for Concurrent Zero-Knowledge in the Bare Public-Key Model.Efficient Non-interactive Range Proof.Approximation Algorithms for Key Management in Secure Multicast.Algorithms.On Smoothed Analysis of Quicksort and Hoare’s Find.On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis.Three New Algorithms for Regular Language Enumeration.Computational Geometry.Convex Partitions with 2-Edge Connected Dual Graphs.The Closest Pair Problem under the Hamming Metric.Space Efficient Multi-dimensional Range Reporting.Approximation Algorithms.Approximation Algorithms for a Network Design Problem.An FPTAS for the Minimum Total Weighted Tardiness Problem with a Fixed Number of DistinctDue Dates.On the Hardness and Approximability of Planar Biconnectivity Augmentation.Computational Biology and Bioinformatics.Determination of Glycan Structure from Tandem Mass Spectra.On the Generalised Character Compatibility Problem for Non-branching Character Trees.Inferring Peptide Composition from Molecular Formulas.Optimal Transitions for Targeted Protein Quantification: Best Conditioned Submatrix Selection.Computing Bond Types in Molecule Graphs.Sampling and Learning.On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries.Finding a Level Ideal of a Poset.A Polynomial-Time Perfect Sampler for the Q-Ising with a Vertex-Independent Noise.Extracting Computational Entropy and Learning Noisy Linear Functions.HITS Can Converge Slowly, but Not Too Slowly, in Score and Rank.Online Tree Node Assignment with Resource Augmentation.Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well.On Finding Small 2-Generating Sets.Convex Recoloring Revisited: Complexity and Exact Algorithms.Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone.Complexity and Computability.Hierarchies and Characterizations of Stateless Multicounter Machines.Efficient Universal Quantum Circuits.An Improved Time-Space Lower Bound for Tautologies.Probabilistic Analysis.Multiple Round Random Ball Placement: Power of Second Chance.The Weighted Coupon Collector’s Problem and Applications.Sublinear-Time Algorithms for Tournament Graphs.Classification of a Class of Counting Problems Using Holographic Reductions.Separating NE from Some Nonuniform Nondeterministic Complexity Classes.On the Readability of Monotone Boolean Formulae.Algorithmsand Data Structures.Popular Matchings: Structure and Algorithms.Graph-Based Data Clustering with Overlaps.Directional Geometric Routing on Mobile Ad Hoc Networks.