Computing and Combinatorics

Inhaltsverzeichnis

• Invited 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.