Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings

Front Matter....Pages -
Market Approach to Social Ads: The MyLikes Example and Related Problems....Pages 1-10
Geodesic-Preserving Polygon Simplification....Pages 11-21
Space-Efficient and Data-Sensitive Polygon Reconstruction Algorithms from Visibility Angle Information....Pages 22-32
On the Edge Crossing Properties of Euclidean Minimum Weight Laman Graphs....Pages 33-43
Structure and Computation of Straight Skeletons in 3-Space....Pages 44-54
Pattern Matching with Non Overlapping Reversals - Approximation and On-line Algorithms....Pages 55-65
Single and Multiple Consecutive Permutation Motif Search....Pages 66-77
Beating $\\mathcal{O}(nm)$ in Approximate LZW-Compressed Pattern Matching....Pages 78-88
Less Space: Indexing for Queries with Wildcards....Pages 89-99
On Determining Deep Holes of Generalized Reed-Solomon Codes....Pages 100-110
Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes....Pages 111-118
Determinantal Complexities and Field Extensions....Pages 119-129
Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs....Pages 130-140
Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs....Pages 141-151
The Complexity of Finding a Large Subgraph under Anonymity Constraints....Pages 152-162
On the Number of Edges of Fan-Crossing Free Graphs....Pages 163-173
Cops and Robbers on Intersection Graphs....Pages 174-184
SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs....Pages 185-195
Hardness and Algorithms for Variants of Line Graphs of Directed Graphs....Pages 196-206
Performance Guarantees for Scheduling Algorithms under Perturbed Machine Speeds....Pages 207-217
Better Bounds for Online k -Frame Throughput Maximization in Network Switches....Pages 218-228
The Solvable Cases of a Scheduling Algorithm....Pages 229-239
Exact Sublinear Binomial Sampling....Pages 240-250
Trivial, Tractable, Hard. A Not So Sudden Complexity Jump in Neighborhood Restricted CNF Formulas....Pages 251-261
Dynamic Point Labeling is Strongly PSPACE-Complete....Pages 262-272
Unsatisfiable CNF Formulas contain Many Conflicts....Pages 273-283
Pursuit Evasion on Polyhedral Surfaces....Pages 284-294
Algorithms for Tolerated Tverberg Partitions....Pages 295-305
Abstract Voronoi Diagrams with Disconnected Regions....Pages 306-316
Terrain Visibility with Multiple Viewpoints....Pages 317-327
Exact Algorithms for Maximum Independent Set....Pages 328-338
On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs....Pages 339-349
Testing Mutual Duality of Planar Graphs....Pages 350-360
Effective and Efficient Data Reduction for the Subset Interconnection Design Problem....Pages 361-371
Myhill-Nerode Methods for Hypergraphs....Pages 372-382
Augmenting Graphs to Minimize the Diameter....Pages 383-393
Top- k Document Retrieval in Compact Space and Near-Optimal Time....Pages 394-404
Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers....Pages 405-412
Trajectory-Based Dynamic Map Labeling....Pages 413-423
Asynchronous Rumor Spreading on Random Graphs....Pages 424-434
Unit Cost Buyback Problem....Pages 435-445
Faster Rumor Spreading with Multiple Calls....Pages 446-456
Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy....Pages 457-467
Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items....Pages 468-478
New Results on the Online Pricing Problem....Pages 479-490
RAM-Efficient External Memory Sorting....Pages 491-501
Succinct Data Structures for Representing Equivalence Classes....Pages 502-512
Sliding Bloom Filters....Pages 513-523
Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs....Pages 524-534
Bounded Representations of Interval and Proper Interval Graphs....Pages 535-546
Detecting and Counting Small Pattern Graphs....Pages 547-557
An O * (1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching....Pages 558-567
New Inapproximability Bounds for TSP....Pages 568-578
Smoothed Analysis of the 2-Opt Heuristic for the TSP: Polynomial Bounds for Gaussian Noise....Pages 579-589
Tight Approximation Bounds for Connectivity with a Color-Spanning Set....Pages 590-600
The Train Delivery Problem Revisited....Pages 601-611
The Distance 4-Sector of Two Points Is Unique....Pages 612-622
The Number of Different Unfoldings of Polyhedra....Pages 623-633
Computing the Smallest Color-Spanning Axis-Parallel Square....Pages 634-643
Euclidean Traveling Salesman Tours through Stochastic Neighborhoods....Pages 644-654
Detecting and Characterizing Small Dense Bipartite-Like Subgraphs by the Bipartiteness Ratio Measure....Pages 655-665
Approximate Čech Complex in Low and High Dimensions....Pages 666-676
Model Counting for Formulas of Bounded Clique-Width....Pages 677-687
Computing Plurality Points and Condorcet Points in Euclidean Space....Pages 688-698
Computing Minimum Tile Sets to Self-Assemble Color Patterns....Pages 699-710
A Probabilistic Analysis of Kademlia Networks....Pages 711-721
Approximating the Generalized Minimum Manhattan Network Problem....Pages 722-732
Minmax Regret 1-Facility Location on Uncertain Path Networks....Pages 733-743
Back Matter....Pages -