Deng / Du Algorithms and Computation

16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings
2005
ISBN: 978-3-540-32426-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 1190 Seiten, eBook

Reihe: Theoretical Computer Science and General Issues

Zielgruppe

Research

Autoren/Hrsg.

Deng, Xiaotie

Du, Dingzhu

Inhaltsverzeichnis

Algorithmic Problems in Wireless Ad Hoc Networks.- Algorithmic Problems in Wireless Ad Hoc Networks.- Probability and Recursion.- Embedding Point Sets into Plane Graphs of Small Dilation.- The Layered Net Surface Problems in Discrete Geometry and Medical Image Segmentation.- Separability with Outliers.- Casting an Object with a Core.- Sparse Geometric Graphs with Small Dilation.- Multiple Polyline to Polygon Matching.- Minimizing a Monotone Concave Function with Laminar Covering Constraints.- Almost Optimal Solutions for Bin Coloring Problems.- GEN-LARAC: A Generalized Approach to the Constrained Shortest Path Problem Under Multiple Additive Constraints.- Simultaneous Matchings.- An Optimization Problem Related to VoD Broadcasting.- A Min-Max Relation on Packing Feedback Vertex Sets.- Average Case Analysis for Tree Labelling Schemes.- Revisiting T. Uno and M. Yagiura’s Algorithm.- Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs.- Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends.- Bisecting a Four-Connected Graph with Three Resource Sets.- Laminar Structure of Ptolemaic Graphs and Its Applications.- On the Complexity of the G-Reconstruction Problem.- Hybrid Voting Protocols and Hardness of Manipulation.- On the Complexity of Rocchio’s Similarity-Based Relevance Feedback Algorithm.- Correlation Clustering and Consensus Clustering.- An Approximation Algorithm for Scheduling Malleable Tasks Under General Precedence Constraints.- A 1.5-Approximation of the Minimal Manhattan Network Problem.- Hardness and Approximation of Octilinear Steiner Trees.- Dense Subgraph Problems with Output-Density Conditions.- A Complete Characterization of Tolerable Adversary Structures for Secure Point-to-Point Transmissions Without Feedback.- Network Game with Attacker and Protector Entities.- SkipTree: A Scalable Range-Queryable Distributed Data Structure for Multidimensional Data.- The Phase Matrix.- ISB-Tree: A New Indexing Scheme with Efficient Expected Behaviour.- External Data Structures for Shortest Path Queries on Planar Digraphs.- Improved Approximate String Matching Using Compressed Suffix Data Structures.- Monitoring Continuous Band-Join Queries over Dynamic Data.- Approximate Colored Range Queries.- Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem.- Space Efficient Algorithms for Ordered Tree Comparison.- A 1.75-Approximation Algorithm for Unsigned Translocation Distance.- Fast Algorithms for Computing the Tripartition-Based Distance Between Phylogenetic Networks.- Improved Algorithms for Largest Cardinality 2-Interval Pattern Problem.- Preemptive Semi-online Scheduling on Parallel Machines with Inexact Partial Information.- On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems.- A Novel Adaptive Learning Algorithm for Stock Market Prediction.- Uniformization of Discrete Data.- A Practical Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions.- Boosting Spectral Partitioning by Sampling and Iteration.- Smoothed Analysis of Binary Search Trees.- Simple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs.- Counting Distinct Items over Update Streams.- Randomized Algorithm for the Sum Selection Problem.- An Improved Interval Routing Scheme for Almost All Networks Based on Dominating Cliques.- Basic Computations in Wireless Networks.- A Simple Optimal Randomized Algorithm for Sorting on the PDM.- Efficient Parallel Algorithms for Constructing a k-Tree Center and a k-Tree Core of a Tree Network.- A Tight Bound on the Number of Mobile Servers to Guarantee the Mutual Transferability Among Dominating Configurations.- Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach.- Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-Width, or Clique-Width.- Sampling Unlabeled Biconnected Planar Graphs.- Configurations with Few Crossings in Topological Graphs.- On Bounded Load Routings for Modeling k-Regular Connection Topologies.- On the Complexity of Global Constraint Satisfaction.- Polynomial Space Suffices for Deciding Nash Equilibria Properties for Extensive Games with Large Trees,.- An Improved -Time Deterministic Algorithm for SAT.- Solving Minimum Weight Exact Satisfiability in Time O(20.2441n ).- Efficient Algorithms for Finding a Longest Common Increasing Subsequence.- Decision Making Based on Approximate and Smoothed Pareto Curves.- Computing Optimal Solutions for the min 3-set covering Problem.- Efficient Algorithms for the Weighted 2-Center Problem in a Cactus Graph.- Algorithms for Local Forest Similarity.- Fast Algorithms for Finding Disjoint Subsequences with Extremal Densities.- A Polynomial Space and Polynomial Delay Algorithm for Enumeration of Maximal Motifs in a Sequence.- 5-th Phylogenetic Root Construction for Strictly Chordal Graphs.- Recursion Theoretic Operators for Function Complexity Classes.- From Balls and Bins to Points and Vertices.- Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs.- Upper Bounds on the Computational Power of an Optical Model of Computation.- Complexity of the Min-Max (Regret) Versions of Cut Problems.- Improved Algorithms for the k Maximum-Sums Problems.- Network Load Games.- Minimum Entropy Coloring.- Algorithms for Max Hamming Exact Satisfiability.- Counting Stable Strategies in Random Evolutionary Games.- Exact and Approximation Algorithms for Computing the Dilation Spectrum of Paths, Trees, and Cycles.- On the Computation of Colored Domino Tilings of Simple and Non-simple Orthogonal Polygons.- Optimal Paths for Mutually Visible Agents.- Stacking and Bundling Two Convex Polygons.- Algorithms for Range-Aggregate Query Problems Involving Geometric Aggregation Operations.- A ( )–Approximation Algorithm for the Stable Marriage Problem.- Approximating the Traffic Grooming Problem.- Scheduling to Minimize Makespan with Time-Dependent Processing Times.- On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems.- Finding a Weight-Constrained Maximum-Density Subtree in a Tree.- Finding Two Disjoint Paths in a Network with Normalized ? ?+?-MIN-SUM Objective Function.- Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time.- Approximation Algorithms for Layered Multicast Scheduling.- Minimum Weight Triangulation by Cutting Out Triangles.- Multi-directional Width-Bounded Geometric Separator and Protein Folding.- Shortest Paths and Voronoi Diagrams with Transportation Networks Under General Distances.- Approximation Algorithms for Computing the Earth Mover’s Distance Under Transformations.- Fast k-Means Algorithms with Constant Approximation.- On Efficient Weighted Rectangle Packing with Large Resources.- On Routing in VLSI Design and Communication Networks.- The Capacitated Traveling Salesman Problem with Pickups and Deliveries on a Tree.- Distance Labeling in Hyperbolic Graphs.- Multi-source Trees: Algorithms for Minimizing Eccentricity Cost Metrics.- Edge-Pancyclicity of Twisted Cubes.- Combinatorial Network Abstraction by Trees and Distances.- Drawing Phylogenetic Trees.- Localized and Compact Data-Structure for Comparability Graphs.- Representation of Graphs by OBDDs.- Space-Efficient Construction of LZ-Index.- Longest Increasing Subsequences in Windows Based on Canonical Antichain Partition.- Errata from ISAAC 2004 (LNCS 3341).- Pareto Optimality in House Allocation Problems.- Generalized Geometric Approaches for Leaf Sequencing Problems in Radiation Therapy,.