
Algorithms and Computation
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
More details
Other editions
Additional editions

Content
- Intro
- Title page
- Preface
- Organization
- Table of Contents
- Invited Talk I
- Algorithm Engineering for Route Planning- An Update -
- References
- Invited Talk II
- Semidefinite Programming and Approximation Algorithms: A Survey
- References
- Approximation Algorithms I
- The School Bus Problem on Trees
- Introduction
- Our Results
- Related Work
- Preliminaries
- A 4-Approximation to the SBP on Trees
- A 12.5-Approximation to the Uncapacitated SBP-R on Trees
- References
- Improved Approximations for Buy-at-Bulk and Shallow-Light k-Steiner Trees and (k, 2)-Subgraph
- Introduction
- Shallow-Light Steiner Trees
- An O(logn)-Approximation for the (k, 2)-Subgraph Problem
- References
- Improved Approximation Algorithms for Routing Shop Scheduling
- Introduction
- Previous Work
- Our Results and Techniques
- Preliminaries
- Routing Open Shop
- Routing Flow Shop
- References
- Contraction-Based Steiner Tree Approximations in Practice
- Introduction
- History
- Contraction Framework
- Algorithm Engineering
- Experiments
- Conclusions and Thoughts
- References
- Computational Geometry I
- Covering and Piercing Disks with Two Centers
- Introduction
- Intersecting Disks with Two Centers
- Decision Algorithm
- Optimization Algorithm
- Covering Disks with Two Centers
- The General Case
- The Restricted Case
- References
- Generating Realistic Roofs over a Rectilinear Polygon
- Introduction
- Preliminaries
- Properties of Realistic Roofs
- Local Properties of Valleys and Ridges
- Global Structure of Realistic Roofs
- Enumerating Realistic Roofs and Computing Optimal Roofs
- References
- Computing the Visibility Polygon Using Few Variables
- Introduction
- Preliminaries
- An O(n) Algorithm Using O(1) Variables
- An O(n logr) Algorithm Using O(logr) Variables
- Closing Remarks
- References
- Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius
- Introduction
- Definitions and Results
- Layered Nearest Neighbor Algorithm
- Bounded Radius Network
- Conclusion
- References
- Graph Algorithms
- Hamiltonian Paths in the Square of a Tree
- Introduction
- Caterpillars and Horsetails
- 2H-Paths in (u,v)-Horsetails
- Efficient Algorithm for Horstail Queries
- References
- Dominating Induced Matchings for P7-free Graphs in Linear Time
- Introduction and Basic Notions
- Simple Properties of Graphs with Dominating Induced Matching
- Structure of P7-free Graphs with Dominating Induced Matching
- Distance Levels with Respect to an M-Edge in a P3
- Edges in and between Ti and Tj, i =j
- The Algorithm for the General P7-free Case
- Conclusion
- References
- Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
- Introduction
- Preliminaries
- Set-Restricted Disjoint Paths
- Contractions and Induced Minors in Chordal Graphs
- Concluding Remarks
- References
- Recognizing Polar Planar Graphs Using New Results for Monopolarity
- Introduction
- Hardness Results
- A 2-SAT Approach and a Superclass of Chair-Free Graphs
- A Superclass of Hole-Free Graphs
- Some Efficiently Solvable Cases of Polarity for Planar Graphs
- Conclusion
- References
- Robustness of Minimum Cost Arborescences
- Introduction
- Fulkerson's Algorithm
- A Sufficient Condition is Necessary
- A Necessary Condition is Sufficient
- References
- Data Structures I
- Path Queries in Weighted Trees
- Introduction
- Previous Work
- Our Results
- Properties of Ordinal Trees
- A Pointer Machine Data Structure
- Optimizations in the RAM model
- Linear Space, but Slower Reporting
- Slightly More Space, Much Faster Reporting
- References
- Dynamic Range Majority Data Structures
- Introduction
- Previous Work
- Our Results
- Dynamic Data Structures in One Dimension
- Supporting Queries
- Supporting Updates
- Speedup for Integer Coordinates
- Dynamic Data Structures in Higher Dimensions
- References
- Dynamic Range Selection in Linear Space
- Introduction
- Previous Work
- Our Results
- Linear Space Data Structure
- Space Efficient Ranking Trees
- Answering Queries
- Handling Updates
- Dynamic Arrays
- Concluding Remarks
- References
- A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time
- Introduction
- A Data Structure with Optimal Query Time
- Compact Representation
- References
- Encoding 2D Range Maximum Queries
- Introduction
- Random Input
- Small m
- Data Structures for 2D-RMQ
- Conclusions and Open Problems
- References
- Distributed Systems
- Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions
- Introduction
- Precise Model and Results
- The Diameter of the Largest Connected Component
- References
- Broadcasting in Heterogeneous Tree Networks with Uncertainty
- Introduction
- Preliminaries
- Finding a Minmax-Regret Broadcast Center
- Correctness
- Time Complexity
- Conclusion
- References
- Optimal File Distribution in Peer-to-Peer Networks
- Introduction
- Homogeneous Symmetric Capacities
- Heterogeneous Symmetric Capacities
- References
- Computational Geometry II
- Animal Testing
- Introduction
- Algorithm 1 Based on Fundamental Polygonsand Davenport-Schinzel Sequences
- Algorithm 2 Based on Euler-Poincaré Formula
- References
- Cutting Out Polygons with a Circular Saw
- Introduction
- Preliminaries
- Algorithm
- References
- Fast Fréchet Queries
- Introduction
- Preliminaries
- The Data Structure
- Making Part of the Query
- Relative Error
- References
- Graph Drawing and Information Visualization
- Angle-Restricted Steiner Arborescences for Flow Map Layout
- Introduction
- Optimal Flux Trees
- Spiral Trees
- Computing Spiral Trees
- Approximating Spiral Trees in the Presenceof Obstacles
- Rectilinear Steiner Arborescences
- Spiral Trees
- References
- Treemaps with Bounded Aspect Ratio
- Introduction
- Convex Treemaps
- Ortho-Convex Treemaps
- Conclusions
- References
- Simultaneous Embedding of Embedded Planar Graphs
- Introduction and Overview
- Preliminaries
- Computing a Sefe-Fe of Three Embedded Planar Graphs
- Sefe-Fe and Sge-Fe of k Embedded Graphs Is NP-Hard
- References
- Linear-Time Algorithms for Hole-Free Rectilinear Proportional Contact Graph Representations
- Introduction
- Representations for Maximal Planar Graphs
- Representations of Planar 3-trees
- Representations for Maximal Outer-Planar Graphs
- Conclusion
- References
- Data Structures II
- Fully Retroactive Approximate Range and Nearest Neighbor Searching
- Introduction
- Related Work
- Our Results
- A General Approach to Retroactivity
- Main Results
- References
- Compact Representation of Posets
- Introduction
- Our Work in Context
- Contributions
- Preliminaries
- Posets
- Transitive Reductions
- Succinct Data Structures
- The Representation
- Storing the Chains
- Storing the Order Relation between Chains
- Operations
- Operation reachability(x,y)
- Operations succG(x) and predG(x)
- Operation range(x,y)
- Operation adjGr(x,y)
- Operations succGr(x) and predGr(x)
- Operations a-succGr(x) and a-predGr(x)
- Operations LUB(x1, ., xt) and GLB(x1, ., xt)
- Operations a-LUB(x1, ., xt) and a-GLB(x1, ., xt)
- Summary and Open Questions
- References
- Explicit Array-Based Compact Data Structures for Triangulations
- Introduction
- Existing Mesh Data Structures
- Preliminaries
- Compactly Representing Triangulations
- The First Data Structure: Simple and Still Redundant
- More Compact Solutions, via Minimal Schnyder Woods
- Further Reducing the Space Requirement
- Experimental Results
- References
- Space-Efficient Data-Analysis Queries on Grids
- Introduction
- Wavelet Trees
- Representation of Grids
- Dynamism
- Statistical Queries
- Range Sum, Average, and Variance
- Range Minima and Maxima
- Range Median and Quantiles
- Range Majority
- Range Successor and Predecessor
- Dynamism
- Final Remarks
- References
- Parameterized Algorithms I
- A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments
- Introduction
- Preliminaries
- Modular Partitions
- Reductions and Kernel
- Data Reduction Rules
- Analysis of Kernel Size
- Conclusion
- References
- Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments
- Introduction
- Preliminaries
- Canonical Sequence for Acyclic Bipartite Tournament
- Allying Sequence of Node Sets and Increasing Subsequence of Node Sets
- Consistent Node Sequence and Compatible Node Sequence
- A Reduction
- Framework of Our Proof for the Main Lemma
- Good Sequence
- Framework for Proving the Main Lemma
- Dynamic Programming for Proving Lemma 4
- References
- Parameterized Algorithms for Inclusion of Linear Matchings
- Introduction
- Problem Definition
- Algorithms for Linear Matching Inclusion
- An FPT Algorithm for Parameters d and k
- An FPT Algorithm for Parameter p
- An Algorithm for Nesting-Free Patterns
- Hardness Results
- Hardness of Linear Matching Inclusion
- Hardness of Nesting-Free 2-Interval Pattern
- References
- Computational Study on Bidimensionality Theory Based Algorithm for Longest Path Problem
- Introduction
- Preliminaries
- Algorithms Implemented
- Computational Results
- Results for Longest Paths
- Results for Grid/Cylinder Minors
- Concluding Remarks
- References
- Parallel and External Memory Algorithms
- Sorting, Searching, and Simulationin the Map Reduce Framework
- Introduction
- Algorithmic Framework for I/O-memory-bound MapReduce
- Simulation Results
- Prefix Sums and Random Indexing
- Multi-searching and Sorting
- References
- External-Memory Multimaps
- Introduction
- External-Memory Cuckoo Hashing
- External-Memory Multimaps
- Experiments
- References
- External Memory Orthogonal Range Reporting with Fast Updates
- Introduction
- Three-Sided Range Reporting for B=(logB4 N)
- Two-Dimensional Range Reporting for B=(log24 N)
- Two-Dimensional Range Reporting for small B
- References
- Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization
- Introduction
- Preliminaries
- Previous Work
- Sorting
- Shortest Paths
- Eulerian Cycles
- Conclusions
- References
- Game Theory and Internet Algorithms
- Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs
- Introduction
- Preliminaries
- PageRank Values
- Directed PageRank games
- Undirected PageRank Games
- Trees
- General Graphs
- Conclusion
- References
- Improved Collaborative Filtering
- Introduction
- Preliminaries
- Algorithm S: Linear Dependence on D
- Complexity Independent of D
- References
- Asymptotic Modularity of Some Graph Classes
- Introduction
- Revisiting Modularity
- Modularity of Decomposable Graphs
- Decomposable graphs
- Multidimensional Torus
- Hypercube
- Unit Ball Graph of a Bounded Growth Metric
- Bounded Growth Metrics
- R-Nets
- Modularity of an R-Net Clustering
- Constant Average Degree Graphs
- Trees of Small Maximum Degree
- Graphs of Average Degree d
- Power-Law Graphs
- Conclusion
- References
- Computational Complexity
- Program Size and Temperature in Self- assembly
- Introduction
- Abstract Tile Assembly Model
- Finding Strengths to Implement a Tile System
- Finding the Minimum Tile Assembly System Assembling a Square at any Temperature
- Bounds on Temperature Relative to Number of Tile Types
- Tile Assembly Systems Requiring Temperature Exponential in Number of Tile Types
- Temperature Linear in the Number of Tile Types Suffices for 2-Cooperative Equivalence
- Open Questions
- References
- Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems
- Maximization by Multiplicative Measure
- Formal Definitions and Basic Properties
- Constraints and Relations
- Optimization Problems with Multiplicative Measures
- Tmax-Constructibility
- Proof of the Main Theorem
- First Step Toward the Proof
- Second Step Toward the Proof
- References
- Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic
- Introduction
- Preliminaries
- DPLL Algorithms with a Cut Heuristic
- Distribution
- Boundary Expanders and the Closure
- Refined Splitting Tree
- References
- Approximation Algorithms II
- Algorithm for Single Allocation Problem on Hub-and-Spoke Networks in 2- Dimensional Plane
- Introduction
- Problem Formulations and Algorithm
- North-West Corner Rule and Dependent Rounding
- Analysis of Approximation Ratio
- Conclusion
- References
- Packing-Based Approximation Algorithm for the k-Set Cover Problem
- Introduction
- Algorithm Description and the Main Theorem
- The Restricted k-Set Packing Algorithm
- Blocking
- Analysis of the Restricted 4-Set Packing Algorithm
- Analysis of the Restricted k-Set Packing Algorithm, k5
- Analysis of the Algorithm PRPSLI
- References
- Capacitated Domination: Constant Factor Approximations for Planar Graphs
- Introduction
- Preliminary
- Constant Approximation for Outer-Planar Graphs
- The Structure
- Removing More Edges
- Greedy Charging Scheme
- Overall Analysis
- Extension to Planar Graphs
- Conclusion
- References
- Randomized Algorithms
- On Power-Law Distributed Balls in Bins and Its Applications to View Size Estimation
- Introduction
- Context
- Model
- Our Contribution
- Bounds for the Expected Number of Balls Needed to Fill All Bins
- Stochastic Majorization Scheme for Finding Bounds
- General Bounds When n1
- Asymptotically Accurate Estimator for the Expected Number of Balls
- Estimating the Expected Number of Occupied Bins Given a Fixed Number of Balls
- Lower Bound
- Upper Bound
- Bound Performance
- Conclusion
- References
- A Randomized Algorithm for Finding Frequent Elements in Streams Using O (log logN) Space
- Introduction
- Preliminary
- Problem Description
- A Basic Idea
- Algorithm
- Other Naïve Algorithms
- Concluding Remark
- References
- A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers
- Introduction
- Adaptive, Non-adaptive, and Canonical Testers
- Graph Blow-Ups and Blow-Up Collections
- Organization of the Paper
- Notation and Basics
- Adaptively Testing BUC(H) Given a Promise
- Proof of Lemma 11
- Non-adaptively Testing BUC(H) Given a Promise
- Removing the Low-Degree Promise
- Conclusions
- References
- Online and Streaming Algorithms
- Online Linear Optimization over Permutations
- Introduction
- Preliminaries
- Algorithm
- Main Structure
- Projection
- Decomposition
- Main Result
- Experimental Results
- Conclusion
- References
- On the Best Possible Competitive Ratio for Multislope Ski Rental
- Introduction
- Problem Statement and Preliminaries
- Infimum of the Best Possible Competitive Ratio
- Supremum of the Best Possible Competitive Ratio
- Subclasses of the Multislope Ski Rental
- References
- Input-Thrifty Extrema Testing
- Introduction
- Input-Thrifty Algorithms
- The Uncertainty Model
- Competitive Analysis
- Extrema Testing
- Preliminaries
- Related Work
- The List Traversal Model
- Intrinsic Cost
- Hyperbolic Sweep
- Conclusion
- References
- Edit Distance to Monotonicity in Sliding Windows
- Introduction
- Formal Problem Definitions
- A (4+)-Approximate Algorithm for Estimating ED
- Estimating R(i)
- Lower Bounds for Out-of-Order Streams
- Estimating ED in an Out-of-Order Stream
- Estimating LIS in an Out-of-Order Stream
- References
- Computational Geometry III
- Folding Equilateral Plane Graphs
- Introduction
- Locked Trees: Not If Equilateral and Linear
- Single-Vertex Origami: Generalization
- Definitions
- Linear Equilateral Trees
- Flat-Foldable Planar Graphs
- NP-Hardness of Graph Folding
- References
- Efficient Algorithms for the Weighted k-Center Problem on a Real Line
- Introduction
- The Algorithmic Scheme
- The Data Structure for Answering (i,j) Queries
- Problem Modeling and Observations
- The Data Structure
- References
- Outlier Respecting Points Approximation
- Introduction
- Statements of Problems
- Our Results
- The Algorithmic Framework
- Algorithmic Components for the Problem RVWSF
- Algorithmic Components for RVPF and RVWPF
- References
- An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles
- Introduction
- Preliminaries
- The Triangle Witness Algorithm
- An Improved Triangle Witness Algorithm
- References
- Parameterized Algorithms II
- The Parameterized Complexity of Local Search for TSP, More Refined
- Introduction
- Basic Notation and Distance Measures
- General Graphs
- Planar Graphs
- Conclusion
- References
- On the Parameterized Complexity of Consensus Clustering
- Introduction
- A Search Tree Algorithm for the Average Mirkin Distance
- NP-Hardness for Input Partitions with a Bounded Number of Clusters
- Hardness of Local Search
- Conclusion
- References
- Two Fixed-Parameter Algorithms for the Cocoloring Problem
- Introduction
- Background and Notation
- (q,q-4)-Graphs
- Graphs with Bounded Treewidth
- References
- Parameterized Complexity of the Firefighter Problem
- Introduction
- Preliminaries
- Parameterized Tractability
- Kernelization Feasibility
- Conclusion
- References
- String Algorithms
- Faster Approximate Pattern Matching in Compressed Repetitive Texts
- Introduction
- Block Graphs
- Fast Random Access in Compressed Space
- Accelerated Approximate Pattern Matching
- Conclusions and Future Work
- References
- A New Algorithm for the Characteristic String Problem under Loose Similarity Criteria
- Introduction
- Preliminaries
- Similarity Criteria
- Algorithm
- Conclusions
- References
- Succinct Indexes for Circular Patterns
- Introduction
- Preliminaries
- Circular Burrows-Wheeler Transform
- Framework for Circular Dictionary Matching
- Succinct Encoding of Circular Suffix Tree
- Parentheses Encoding of STc
- Height Array
- Circular Dictionary Matching with Our Index
- References
- Range LCP
- Introduction
- An Algorithm Linear in the Range Length
- Finding the Pair with the Longest Common Prefix
- An Efficient Range LCP Algorithm
- Constructing the Optimal Bridges
- Finding the Smallest Bridge in an Interval
- References
- Optimization
- Computing Knapsack Solutions with Cardinality Robustness
- Introduction
- NP-Hardness for the Max-Robust Knapsack Problem
- Simple Pseudo-Polynomial Time Algorithm
- Improved Pseudo-Polynomial Time Algorithm
- Fully Polynomial Time Approximation Scheme
- References
- Max-Throughput for (Conservative) k-of-n Testing
- Introduction
- Related Work
- Problem Definitions
- The Algorithm for the MinCost Problem
- The Algorithm for the CMT(k) Problem
- The Equal Rates Case
- The Equalizing Algorithm of Condon et al.
- An Equalizing Algorithm for the CMT(k) Problem
- An Ellipsoid-Based Algorithm for the SMT(k) Problem
- References
- Closest Periodic Vectors in Lp Spaces
- Introduction
- Preliminaries
- Closest Periodic Vectors in L1, L2 and L Spaces
- Closest Periodic Vector in L2 Space
- Closest Periodic Vector in L Space
- Closest Periodic Vector in L1 Space
- Fast Approximations of the Closest Periodic Vector in L1, L2 and L Spaces
- Approximation in L2 Space
- Approximation in L1 Space
- Approximation in L Space
- References
- Maximum Weight Digital Regions Decomposable into Digital Star-Shaped Regions
- Introduction
- The Algorithm
- Experiments
- NP-Completeness
- References
- Computational Biology
- Finding Maximum Sum Segments in Sequences with Uncertainty
- Introduction
- Notation and Preliminaries
- The Length-Relaxed MSSU Problem
- Preprocessing
- Basic Algorithm
- Improved Algorithm
- The Length-Constrained MSSU Problem
- Concluding Remarks
- References
- Algorithms for Building Consensus MUL-trees
- Introduction
- Definitions
- Our Results and Organization of the Paper
- Preliminaries
- Building a Strict Consensus MUL-tree
- Building a Majority Rule Consensus MUL-tree
- Building a Singular Majority Rule Consensus MUL-tree
- References
- Adaptive Phenotype Testing for AND/OR Items
- Introduction
- Our Contributions
- Preliminaries
- APT Algorithms for General k and d
- One Phenotype (k = 1, d 1)
- Multiple Phenotype (k 2 and d 1)
- APT Algorithms for Special k and d
- k = 1 and d = 2
- k 1 and d = 1
- k = 2 and d = 2
- Conclusions
- References
- An Index Structure for Spaced Seed Search
- Introduction
- Preliminaries
- Definitions and Notations
- Search Method
- Constructing the b-Suffix Array for Given T and b
- Underlying Ideas
- O(gn)-Time, O(n)-Space Algorithm
- O(wnlogw)-Time and O(wn)-Space Algorithm
- Constructing b-Suffix Arrays for Periodic b
- Conclusion
- References
- Author Index
System requirements
File format: PDF
Copy protection: Watermark-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Use the free software Adobe Reader, Adobe Digital Editions, or any other PDF viewer of your choice (see eBook Help).
- Tablet/Smartphone (Android; iOS): Install the free app Adobe Digital Editions or another reading app for eBooks, e.g., PocketBook (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Watermark-DRM, a „soft” copy protection. This means that there are no technical restrictions to prevent illegal distribution. However, there is a personalised watermark embedded in the eBook that can be used to identify the purchaser of the eBook in the event of misuse and to provide evidence for legal purposes.
For more information, see our eBook Help page.