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

Invited Talk Paper.- Market Approach to Social Ads: The MyLikes Example
and Related Problems.- Session 1A: Computational Geometry I.-
Geodesic-Preserving Polygon Simplification.- Space-Efficient and
Data-Sensitive Polygon Reconstruction Algorithms from Visibility Angle
Information.- On the Edge Crossing Properties of Euclidean Minimum Weight
Laman Graphs.- Structure and Computation of Straight Skeletons in 3-Space.-
Session 1B: Pattern Matching.- Pattern Matching with Non Overlapping
Reversals Approximation and On-line Algorithms.- Single and Multiple
Consecutive Permutation Motif Search.- Beating O(nm) in Approximate
LZW-Compressed Pattern Matching.- Less Space: Indexing for Queries with
Wildcards.- Session 2A: Computational Complexity I.- On Determining Deep
Holes of Generalized Reed-Solomon Codes.- Isomorphism on Subgraph-Closed
Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes.-
Determinantal Complexities and Field Extensions.- Session 2B: Internet and
Social Network Algorithms I.- Algorithms to Measure Diversity and Clustering
in Social Networks through Dot Product Graphs.- Sublinear-Time Algorithms for
Monomer-Dimer Systems on Bounded Degree Graphs.- The Complexity of Finding a
Large Subgraph under Anonymity Constraints.- Session 3A: Graph Theory and
Algorithms I.- On the Number of Edges of Fan-Crossing Free Graphs.- Cops and
Robbers on Intersection Graphs.- SEFE with No Mapping via Large Induced
Outerplane Graphs in Plane Graph.- Hardness and Algorithms for Variants of
Line Graphs of Directed Graphs.- Session 3B: Scheduling Algorithms.-
Performance Guarantees for Scheduling Algorithms under Perturbed Machine
Speeds.- Better Bounds for Online k-Frame Throughput Maximization in Network
Switches.- The Solvable Cases of a Scheduling Algorithm.- Session 4A:
Computational Complexity II.- Exact Sublinear Binomial Sampling.- Trivial,
Tractable, Hard. A Not So Sudden Complexity Jump in Neighborhood Restricted
CNF Formulas.- Dynamic PointLabeling 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.