Algorithms and Computation: 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings

Front Matter....Pages -
Future Directions in Computer Science Research....Pages 1-1
Combinatorial Geometry and Approximation Algorithms....Pages 2-2
Origami Robots and Star Trek Replicators....Pages 3-3
Strong Conflict-Free Coloring for Intervals....Pages 4-13
Closing Complexity Gaps for Coloring Problems on H -Free Graphs....Pages 14-23
Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors....Pages 24-33
Reconfiguration of List L (2,1)-Labelings in a Graph....Pages 34-43
An 8/3 Lower Bound for Online Dynamic Bin Packing....Pages 44-53
Computing k -center over Streaming Data for Small k ....Pages 54-63
Precision vs Confidence Tradeoffs for ℓ 2 -Based Frequency Estimation in Data Streams....Pages 64-74
Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem....Pages 75-84
A Partially Ordered Structure and a Generalization of the Canonical Partition for General Graphs with Perfect Matchings....Pages 85-94
Fast and Simple Fully-Dynamic Cut Tree Construction....Pages 95-105
Green Scheduling, Flows and Matchings....Pages 106-115
Popular and Clan-Popular b -Matchings....Pages 116-125
Kernelization and Parameterized Complexity of Star Editing and Union Editing....Pages 126-135
On the Advice Complexity of Buffer Management....Pages 136-145
On the Complexity of the Maximum Common Subgraph Problem for Partial k -Trees of Bounded Degree....Pages 146-155
Speeding Up Shortest Path Algorithms....Pages 156-165
How Many Potatoes Are in a Mesh?....Pages 166-176
On Higher Order Voronoi Diagrams of Line Segments....Pages 177-186
On the Farthest Line-Segment Voronoi Diagram....Pages 187-196
Computing the Longest Common Subsequence of Two Run-Length Encoded Strings....Pages 197-206
Efficient Counting of Square Substrings in a Tree....Pages 207-216
A General Method for Improving Insertion-Based Adaptive Sorting....Pages 217-226
Counting Partitions of Graphs....Pages 227-236
Constant Unary Constraints and Symmetric Real-Weighted Counting CSPs....Pages 237-246
Interval Scheduling and Colorful Independent Sets....Pages 247-256
More on a Problem of Zarankiewicz....Pages 257-266
Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs....Pages 267-277
On the Hyperbolicity of Small-World and Tree-Like Random Graphs....Pages 278-288
On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets....Pages 289-298
Induced Immersions....Pages 299-308
Rectilinear Covering for Imprecise Input Points....Pages 309-318
Robust Nonparametric Data Approximation of Point Sets via Data Reduction....Pages 319-331
Optimal Point Movement for Covering Circular Regions....Pages 332-341
Solving Circular Integral Block Decomposition in Polynomial Time....Pages 342-351
The Canadian Traveller Problem Revisited....Pages 352-361
Vehicle Scheduling on a Graph Revisited....Pages 362-371
A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks....Pages 372-381
The Minimum Vulnerability Problem....Pages 382-391
A Strongly Polynomial Time Algorithm for the Shortest Path Problem on Coherent Planar Periodic Graphs....Pages 392-401
Cubic Augmentation of Planar Graphs....Pages 402-412
On the Number of Upward Planar Orientations of Maximal Planar Graphs....Pages 413-422
Universal Point Subsets for Planar Graphs....Pages 423-432
Abstract Flows over Time: A First Step towards Solving Dynamic Packing Problems....Pages 433-443
Extending Partial Representations of Subclasses of Chordal Graphs....Pages 444-454
Isomorphism for Graphs of Bounded Connected-Path-Distance-Width....Pages 455-464
Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph....Pages 465-474
Linear Layouts in Submodular Systems....Pages 475-484
Segmental Mapping and Distance for Rooted Labeled Ordered Trees....Pages 485-494
Detecting Induced Minors in AT-Free Graphs....Pages 495-505
Degree-Constrained Orientations of Embedded Graphs....Pages 506-516
Interval Graph Representation with Given Interval and Intersection Lengths....Pages 517-526
Finger Search in the Implicit Model....Pages 527-536
A Framework for Succinct Labeled Ordinal Trees over Large Alphabets....Pages 537-547
A Space-Efficient Framework for Dynamic Point Location....Pages 548-557
Selection in the Presence of Memory Faults, with Applications to In-place Resilient Sorting....Pages 558-567
An Improved Algorithm for Static 3D Dominance Reporting in the Pointer Machine....Pages 568-577
The Multi-Service Center Problem....Pages 578-587
Computing Minmax Regret 1-Median on a Tree Network with Positive/Negative Vertex Weights....Pages 588-597
Fence Patrolling by Mobile Agents with Distinct Speeds....Pages 598-608
Weak Visibility Queries of Line Segments in Simple Polygons....Pages 609-618
Beyond Homothetic Polygons: Recognition and Maximum Clique....Pages 619-628
Area Bounds of Rectilinear Polygons Realized by Angle Sequences....Pages 629-638
A Time-Efficient Output-Sensitive Quantum Algorithm for Boolean Matrix Multiplication....Pages 639-648
On Almost Disjunct Matrices for Group Testing....Pages 649-658
Parameterized Clique on Scale-Free Networks....Pages 659-668
Multi-unit Auctions with Budgets and Non-uniform Valuations....Pages 669-678
Efficient Computation of Power Indices for Weighted Majority Games....Pages 679-689
Revenue Maximization in a Bayesian Double Auction Market....Pages 690-699
Back Matter....Pages -