
WALCOM: 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
- Title Page
- Preface
- Organization
- Table of Contents
- Invited Talks
- Geometry and Topology from Point Cloud Data
- The Disjoint Paths Problem: Algorithm and Structure
- Background
- Results
- When k (The Number of Terminals) Is Bounded
- Approximation
- Purely Combinatorial Results
- The Physarum Computer
- Approximation Algorithms
- Maximum Betweenness Centrality: Approximability and Tractable Cases
- Introduction
- Approximation Algorithms
- Tight Examples
- APX-Completeness
- A Polynomial-Time Algorithm for Trees
- Concluding Remarks
- Approximation Algorithms for Minimum Chain Vertex Deletion
- Introduction
- Notations and Known Results
- Approximation Algorithms
- 3-Factor Approximation Algorithm
- Second 3-Factor Approximation Algorithm
- 2-Factor Approximation Algorithm
- Maximum Vertex Induced Chain Subgraph
- Hardness Results
- Conclusion and Further Directions
- Oblivious Buy-at-Bulk in Planar Graphs
- Introduction
- Problem Statement
- Contribution
- Related Work
- Definitions
- Sparse Cover
- Algorithm
- Analysis
- Conclusions
- Hardness
- The Complexity of Acyclic Subhypergraph Problems
- Introduction
- Definitions
- Spanning Acyclic Subhypergraphs
- NP-Completeness for , and -Acyclicity
- Maximum Acyclic Subhypergraphs
- A Method to Determine the Degree of Polynomial Relatively to a Subset of Its Variables
- Application of the Method
- NP-Complete Cases
- Conclusion
- Inapproximability of b-Matching in k-Uniform Hypergraphs
- Introduction
- The Maximum b-Matching Problem: Definition and Previous Work
- Preliminaries and Definitions
- The Reduction from Max-E3-Lin-q and Non-approximability
- The Reduction
- Proof of the Non-approximability
- Proof of the Structure Theorem (Theorem 2)
- Open Problems
- k-Level Crossing Minimization Is NP-Hard for Trees
- Introduction
- 2-Leveled Trees with One Level Fixed
- k-Leveled Trees
- Conclusions
- References
- Algorithm Engineering
- Efficient Computation of Time-Dependent Centralities in Air Transportation Networks
- Introduction
- Time-Dependent Network Model
- Centrality
- Experiments
- Conclusions and Future Work
- References
- Analysis of Gauss-Sieve for Solving theShortest Vector Problem in Lattices
- Introduction
- Preliminaries
- Experiments
- Sieving for Different Types of Lattices
- New Algorithm Characteristics
- Chronological Behaviour of Gauss Sieve
- Gauss Sieving with Known Goal-Norm
- Pre-reducing Lattices
- Conclusion
- Computational Geometry
- Minimum Enclosing Circle of a Set of Fixed Points and a Mobile Point
- Introduction
- Characterization the Center Function
- Properties of the Radius Function
- C(S) =
- C(S) =
- Computation of the Center Function
- Conclusions
- Efficient Top-k Queries for Orthogonal Ranges
- Introduction
- Related Work
- Formal Problem Statement
- Dynamic Structure for Reporting Top-k Points in Arbitrary Order
- Handling Insertions and Deletions
- Reporting Top-k Points in Sorted Order
- Solution for IR1
- Solution for IRd, d2
- Conclusions and Future Work
- Range-Aggregate Queries Involving Geometric Aggregation Operations
- Introduction
- Our Contribution
- Static Range-Aggregate Point Enclosure
- One-Dimensional Scenario
- Extension to Higher Dimensions (d 2)
- Semi-dynamic Range-Aggregate Point Enclosure
- One-Dimensional Scenario
- Extending It to Higher Dimensions
- 1-d Range-Aggregate Segment Intersection
- Static Solution
- Semi-dynamic Solution
- Range-Aggregate Orthogonal Segment Intersection
- Range-Aggregate Orthogonal Segment Intersection with Distant Constraint
- Approximation Algorithms
- Multi Cover of a Polygon Minimizing the Sum of Areas
- Introduction
- Related Work
- Our Results
- k-Cover of Polygon
- k-Cover of Points
- k-Cover of Polygon
- On the Discrete Unit Disk Cover Problem
- Introduction
- Our Results
- Related Work
- Preliminaries
- Testing Feasibility
- Discrete Unit Disk Cover Problem
- Within Strip Problem
- Outside Strip Point Cover Problem
- Conclusion
- References
- Clustering with Internal Connectedness
- Introduction
- Problem Definition and Notation
- Related Work
- Our Results
- Hardness of Approximation
- An O(logn)-Approximation Algorithm
- Reduction to the CSCP Problem
- Approximating the CSCP Problem
- String Algorithms
- Hashed Patricia Trie: Efficient Longest Prefix Matching in Peer-to-Peer Systems
- Introduction
- Related Work
- Our Contribution: Hashed Patricia Trie
- Patricia Trie
- Hashed Patricia Trie
- Applications
- Operations
- PrefixSearch(x)
- Insert(x)
- Delete(x)
- Complexity Analysis
- Conclusion
- De Bruijn Sequences for the Binary Strings with Maximum Density
- Introduction
- Background
- Construction
- Algorithm
- Open Problems
- Graph Algorithms
- A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs
- Introduction
- Preliminaries
- Biconvex Orderings and Monotone Paths
- Ordering of Vertices
- Monotonic Path
- The Algorithm and Correctness
- Some Constructs and Notations Used in the Algorithm
- Algorithm
- Proof of Correctness
- Correctness Argument
- Time Complexity
- Conclusion and Further Work
- Counting Spanning Trees in Graphs Using Modular Decomposition
- Introduction
- Preliminaries
- The Main Idea and the Contraction Process
- The Algorithm
- Processing Basic Graphs
- Counting Spanning Trees in Linear Time
- Concluding Remarks
- References
- On Graceful Labelings of Trees
- Introduction
- Preliminaries
- Graceful Labeling
- Conclusion
- Minimum-Layer Drawings of Trees
- Introduction
- Preliminaries
- Root-Visible Drawings of Trees
- Minimum-Layer Drawings
- Conclusion
- 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.