Algorithms and Computation: 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005. Proceedings

Front Matter....Pages -
Algorithmic Problems in Wireless Ad Hoc Networks....Pages 1-1
Probability and Recursion....Pages 2-4
Embedding Point Sets into Plane Graphs of Small Dilation....Pages 5-16
The Layered Net Surface Problems in Discrete Geometry and Medical Image Segmentation....Pages 17-27
Separability with Outliers....Pages 28-39
Casting an Object with a Core....Pages 40-49
Sparse Geometric Graphs with Small Dilation....Pages 50-59
Multiple Polyline to Polygon Matching....Pages 60-70
Minimizing a Monotone Concave Function with Laminar Covering Constraints....Pages 71-81
Almost Optimal Solutions for Bin Coloring Problems....Pages 82-91
GEN-LARAC: A Generalized Approach to the Constrained Shortest Path Problem Under Multiple Additive Constraints....Pages 92-105
Simultaneous Matchings....Pages 106-115
An Optimization Problem Related to VoD Broadcasting....Pages 116-125
A Min-Max Relation on Packing Feedback Vertex Sets....Pages 126-135
Average Case Analysis for Tree Labelling Schemes....Pages 136-145
Revisiting T. Uno and M. Yagiura’s Algorithm....Pages 146-155
Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs....Pages 156-165
Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends....Pages 166-175
Bisecting a Four-Connected Graph with Three Resource Sets....Pages 176-185
Laminar Structure of Ptolemaic Graphs and Its Applications....Pages 186-195
On the Complexity of the G -Reconstruction Problem....Pages 196-205
Hybrid Voting Protocols and Hardness of Manipulation....Pages 206-215
On the Complexity of Rocchio’s Similarity-Based Relevance Feedback Algorithm....Pages 216-225
Correlation Clustering and Consensus Clustering....Pages 226-235
An Approximation Algorithm for Scheduling Malleable Tasks Under General Precedence Constraints....Pages 236-245
A 1.5-Approximation of the Minimal Manhattan Network Problem....Pages 246-255
Hardness and Approximation of Octilinear Steiner Trees....Pages 256-265
Dense Subgraph Problems with Output-Density Conditions....Pages 266-276
A Complete Characterization of Tolerable Adversary Structures for Secure Point-to-Point Transmissions Without Feedback....Pages 277-287
Network Game with Attacker and Protector Entities....Pages 288-297
SkipTree: A Scalable Range-Queryable Distributed Data Structure for Multidimensional Data....Pages 298-307
The Phase Matrix....Pages 308-317
ISB-Tree: A New Indexing Scheme with Efficient Expected Behaviour....Pages 318-327
External Data Structures for Shortest Path Queries on Planar Digraphs....Pages 328-338
Improved Approximate String Matching Using Compressed Suffix Data Structures....Pages 339-348
Monitoring Continuous Band-Join Queries over Dynamic Data....Pages 349-359
Approximate Colored Range Queries....Pages 360-369
Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem....Pages 370-379
Space Efficient Algorithms for Ordered Tree Comparison....Pages 380-391
A 1.75-Approximation Algorithm for Unsigned Translocation Distance....Pages 392-401
Fast Algorithms for Computing the Tripartition-Based Distance Between Phylogenetic Networks....Pages 402-411
Improved Algorithms for Largest Cardinality 2-Interval Pattern Problem....Pages 412-421
Preemptive Semi-online Scheduling on Parallel Machines with Inexact Partial Information....Pages 422-432
On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems....Pages 433-442
A Novel Adaptive Learning Algorithm for Stock Market Prediction....Pages 443-452
Uniformization of Discrete Data....Pages 453-462
A Practical Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions....Pages 463-472
Boosting Spectral Partitioning by Sampling and Iteration....Pages 473-482
Smoothed Analysis of Binary Search Trees....Pages 483-492
Simple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs....Pages 493-504
Counting Distinct Items over Update Streams....Pages 505-514
Randomized Algorithm for the Sum Selection Problem....Pages 515-523
An Improved Interval Routing Scheme for Almost All Networks Based on Dominating Cliques....Pages 524-532
Basic Computations in Wireless Networks....Pages 533-542
A Simple Optimal Randomized Algorithm for Sorting on the PDM....Pages 543-552
Efficient Parallel Algorithms for Constructing a k -Tree Center and a k -Tree Core of a Tree Network....Pages 553-562
A Tight Bound on the Number of Mobile Servers to Guarantee the Mutual Transferability Among Dominating Configurations....Pages 563-572
Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach....Pages 573-582
Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-Width, or Clique-Width....Pages 583-592
Sampling Unlabeled Biconnected Planar Graphs....Pages 593-603
Configurations with Few Crossings in Topological Graphs....Pages 604-613
On Bounded Load Routings for Modeling k -Regular Connection Topologies....Pages 614-623
On the Complexity of Global Constraint Satisfaction....Pages 624-633
Polynomial Space Suffices for Deciding Nash Equilibria Properties for Extensive Games with Large Trees,....Pages 634-643
An Improved $\tilde{\mathcal{O}}(1.234^{m})$ -Time Deterministic Algorithm for SAT....Pages 644-653
Solving Minimum Weight Exact Satisfiability in Time O (2 0.2441n )....Pages 654-664
Efficient Algorithms for Finding a Longest Common Increasing Subsequence....Pages 665-674
Decision Making Based on Approximate and Smoothed Pareto Curves....Pages 675-684
Computing Optimal Solutions for the min 3-set covering Problem....Pages 685-692
Efficient Algorithms for the Weighted 2-Center Problem in a Cactus Graph....Pages 693-703
Algorithms for Local Forest Similarity....Pages 704-713
Fast Algorithms for Finding Disjoint Subsequences with Extremal Densities....Pages 714-723
A Polynomial Space and Polynomial Delay Algorithm for Enumeration of Maximal Motifs in a Sequence....Pages 724-737
5-th Phylogenetic Root Construction for Strictly Chordal Graphs....Pages 738-747
Recursion Theoretic Operators for Function Complexity Classes....Pages 748-756
From Balls and Bins to Points and Vertices....Pages 757-766
Simulating Undirected st -Connectivity Algorithms on Uniform JAGs and NNJAGs....Pages 767-776
Upper Bounds on the Computational Power of an Optical Model of Computation....Pages 777-788
Complexity of the Min-Max (Regret) Versions of Cut Problems....Pages 789-798
Improved Algorithms for the k Maximum-Sums Problems....Pages 799-808
Network Load Games....Pages 809-818
Minimum Entropy Coloring....Pages 819-828
Algorithms for Max Hamming Exact Satisfiability....Pages 829-838
Counting Stable Strategies in Random Evolutionary Games....Pages 839-848
Exact and Approximation Algorithms for Computing the Dilation Spectrum of Paths, Trees, and Cycles....Pages 849-858
On the Computation of Colored Domino Tilings of Simple and Non-simple Orthogonal Polygons....Pages 859-868
Optimal Paths for Mutually Visible Agents....Pages 869-881
Stacking and Bundling Two Convex Polygons....Pages 882-891
Algorithms for Range-Aggregate Query Problems Involving Geometric Aggregation Operations....Pages 892-901
A ( $2 - c{{1} \over {\sqrt{N}}}$ )–Approximation Algorithm for the Stable Marriage Problem....Pages 902-914
Approximating the Traffic Grooming Problem....Pages 915-924
Scheduling to Minimize Makespan with Time-Dependent Processing Times....Pages 925-933
On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems....Pages 934-943
Finding a Weight-Constrained Maximum-Density Subtree in a Tree....Pages 944-953
Finding Two Disjoint Paths in a Network with Normalized α  +  -MIN-SUM Objective Function....Pages 954-963
Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time....Pages 964-973
Approximation Algorithms for Layered Multicast Scheduling....Pages 974-983
Minimum Weight Triangulation by Cutting Out Triangles....Pages 984-994
Multi-directional Width-Bounded Geometric Separator and Protein Folding....Pages 995-1006
Shortest Paths and Voronoi Diagrams with Transportation Networks Under General Distances....Pages 1007-1018
Approximation Algorithms for Computing the Earth Mover’s Distance Under Transformations....Pages 1019-1028
Fast k-Means Algorithms with Constant Approximation....Pages 1029-1038
On Efficient Weighted Rectangle Packing with Large Resources....Pages 1039-1050
On Routing in VLSI Design and Communication Networks....Pages 1051-1060
The Capacitated Traveling Salesman Problem with Pickups and Deliveries on a Tree....Pages 1061-1070
Distance Labeling in Hyperbolic Graphs....Pages 1071-1079
Multi-source Trees: Algorithms for Minimizing Eccentricity Cost Metrics....Pages 1080-1089
Edge-Pancyclicity of Twisted Cubes....Pages 1090-1099
Combinatorial Network Abstraction by Trees and Distances....Pages 1100-1109
Drawing Phylogenetic Trees....Pages 1110-1121
Localized and Compact Data-Structure for Comparability Graphs....Pages 1122-1131
Representation of Graphs by OBDDs....Pages 1132-1142
Space-Efficient Construction of LZ-Index....Pages 1143-1152
Longest Increasing Subsequences in Windows Based on Canonical Antichain Partition....Pages 1153-1162
Pareto Optimality in House Allocation Problems....Pages 1163-1175
Generalized Geometric Approaches for Leaf Sequencing Problems in Radiation Therapy,....Pages 1176-1186
Back Matter....Pages -