Algorithms and Computation

is Strongly PSPACE-Complete.- Unsatisfiable CNF Formulas Contain Many Conflicts.- Session 4B: Computational Geometry II.- Pursuit Evasion on Polyhedral Surfaces.- Algorithms for Tolerated Tverberg Partitions.- Abstract Voronoi Diagrams with Disconnected Regions.- Terrain Visibility with Multiple Viewpoints.- Session 5A: Graph Theory and Algorithms II.- Exact Algorithms for Maximum Independent Set.- On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs.- Testing Mutual Duality of Planar Graph .- Session 5B: Fixed-Parameter Tractable Algorithms.- Effective and Efficient Data Reduction for the Subset Interconnection Design Problem.- Myhill-Nerode Methods for Hypergraphs.- Augmenting Graphs to Minimize the Diameter.- Session 6A: Algorithms and Data Structures I.- Top-k Document Retrieval in Compact Space and Near-Optimal Time.- Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers.- Trajectory-Based Dynamic Map Labeling.- Session 6B: Internet and Social Network.- Algorithms II.- Asynchronous Rumor Spreading on Random Graphs.- Unit Cost Buyback Problem.- Faster Rumor Spreading with Multiple Calls.- Session 7A: Algorithmic Game Theory.- Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy.- Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items.- New Results on the Online Pricing Problem.- Session 7B: Algorithms and Data Structures II.- RAM-Efficient External Memory Sorting.- Succinct Data Structures for Representing Equivalence Classes.- Sliding Bloom Filters.- Session 8A: Graph Theory and Algorithms III.- Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs.- Bounded Representations of Interval and Proper Interval Graphs.- Detecting and Counting Small Pattern Graphs.- An O (1.1939n) Time Algorithm for Minimum Weighted Dominating Induced Matching.- Session 8B: Approximation Algorithms I.- New InapproximabilityBounds for TSP.- Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise.- Tight Approximation Bounds for Connectivity with a Color-Spanning Set.- The Train Delivery Problem Revisited.- Session 9A: Computational Geometry III.- The Distance 4-Sector of Two Points Is Unique.- The Number of Different Unfoldings of Polyhedra.- Computing the Smallest Color-Spanning Axis-Parallel Square.- Session 9B: Approximation Algorithms II.- Euclidean Traveling Salesman Tours through Stochastic Neighborhoods.- Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure.- Approximate Cech Complex in Low and High Dimensions.- Session 10A: Computational Complexity III.- Model Counting for Formulas of Bounded Clique- Width.- Computing Plurality Points and Condorcet Points in Euclidean Space.- Computing Minimum Tile Sets to Self-assemble Color Patterns.- Session 10B: Network Algorithms.- A Probabilistic Analysis of Kademlia Networks.- Approximating the Generalized Minimum Manhattan Network Problem.- Minmax Regret 1-Facility Location on Uncertain Path Networks.