
WALCOM: Algorithm 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 Talks
- Combinatorial Optimization with Noisy Inputs: How Can We Separate the Wheat from the Chaff?
- Approximability of Stable Matching Problems
- On Three-Dimensional Graph Drawing and Embedding
- Introduction
- References
- Graph Algorithms I
- Bounding the Number of Reduced Trees, Cographs, and Series-Parallel Graphsby Compression
- Introduction
- Preliminaries
- Compact Representation of Unordered Reduced Trees
- Encoding an Unordered Reduced Tree
- Decoding an Unordered Reduced Tree
- Compact Representation of Cographs
- Compact Representation of Series-Parallel Graphs
- Conclusion
- References
- Generalized Above Guarantee Vertex Coverand $r$ -Partization
- Introduction
- Generalized above Guarantee Vertex Cover Is Hard
- Parameterized r-Partization in Special Graph Classes
- $r$ -Partization in Perfect Graphs
- $r$ -Partization in Split Graphs
- $r$ -Partization in Treewidth-Bounded Graphs
- OCT in Perfect Graphs
- Concluding Remarks
- References
- Computational Geometry
- Farthest Voronoi Diagrams under Travel Time Metrics
- Introduction
- Preliminaries
- Complexity Bound of the Farthest Voronoi Diagram
- Computing the Farthest Voronoi Diagram
- Finding Vertices on Open Merge Curves
- Finding Vertices on Closed Merge Curves
- References
- Tight Bound for Farthest-Color Voronoi Diagrams of Line Segments
- Introduction
- Preliminaries
- Line Segment Voronoi Diagrams
- Definition of Farthest-Color Voronoi Diagrams
- Tight Bound on the Complexity of FCVD(S)
- Upper Bound Proof
- Lower Bound Construction
- Algorithm
- Review on the Algorithm of Huttenlocher et al.
- Our Analysis
- References
- Range Aggregate Maximal Points in the Plane
- Introduction
- Preliminaries
- Our Contributions
- The Reporting Problem
- Preprocessing for the Reporting Problem
- Query Algorithm
- The Counting Problem
- Preprocessing for the Counting Problem
- Query Algorithm
- Case (i): p'x= p'''x= p x
- Case (ii): $p''' x= p'x= px$
- References
- Approximation Algorithms
- Approximating the Multi-level Bottleneck Assignment Problem
- Introduction
- The Complexity of MBA
- The Approximability of MBA3
- The Sequential Bottleneck Heuristic (SB)
- An Inapproximability Result
- A 32-Approximation Algorithm for MBA3 with a Single Complete Edge Set
- The Description of Heuristic AB
- The Analysis of Heuristic AB
- A Polynomial Time Approximation Scheme for Complete-MBA
- Online Algorithms for MBA
- References
- Reoptimization of the Maximum Weighted P_ k-Free Subgraph Problem under Vertex Insertion
- Introduction
- max weighted Pk-free subgraph
- Reoptimization and bin packing
- Conclusion
- References
- Comparing and Aggregating Partial Orders with Kendall Tau Distances
- Introduction
- Preliminaries
- Distance Problems: Intractability, Approximation and Fixed Parameter Tractability
- Rank Aggregation Problems
- Conclusion and Open Problems
- References
- Graph Algorithms II
- On the Round-Trip 1-Center and 1-Median Problems
- Introduction
- Notation and Preliminaries
- The Restricted Round-Trip 1-Center Problem
- Tamir and Halman's Algorithm
- An Improved Algorithm
- Theorem 1.
- The All-Pairs Best-Depots Problem
- The Restricted Round-Trip 1-Median Problem
- Concluding Remarks
- References
- Triangle-Free Outerplanar 3-Graphs Are Pairwise Compatibility Graphs
- Introduction
- Preliminaries
- Outer Subdivisions of Ladder Graphs and PCGs
- Triangle-Free Outerplanar 3-Graphs Are PCGs
- Triangle-Free Biconnected Outerplanar 3-Graphs
- Triangle-Free Outerplanar 3-Graphs
- Conclusion
- References
- On Relaxing the Constraints in Pairwise Compatibility Graphs
- Introduction
- Preliminaries
- Relationships between PCG, LPG and mLPG
- PCG $\supset$ LPG $ \cup$ mLPG
- LPG $\cap$ mLPG $\neq \emptyset$
- LPG \ mLPG \neq \emptyset and mLPG LPG $\neq \emptyset $
- Split Matrogenic Graphs
- Conclusions and Open Problems
- References
- Graph Drawing I
- Universal Line-Sets for Drawing Planar 3-Trees
- Introduction
- Preliminaries
- Drawings on Parallel Lines and Concentric Circles
- Universal Line Sets for Drawing Planar 3-Trees
- Bounds for Special Classes of Planar 3-Trees
- Conclusion
- References
- On the Hardness of P oint-Set Embeddability
- Introduction
- Preliminaries
- Point-Set Embeddings of 3-Connected Planar Graphs
- Convex Point-Set Embeddings of Klee Graphs
- Open Problems
- References
- String and Data Structures
- Linear Time Inference of Strings from CoverArrays Using a Binary Alphabet
- Introduction
- Preliminaries
- Problem Definition and Important Properties
- Our Algorithm
- Experimental Results
- Conclusion
- References
- Fat Heaps without Regular Counters
- Introduction
- Fat Heaps Simplified
- Implementation Enhancements
- Experiments
- Conclusion
- References
- Graph Drawing II
- Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles
- Introduction
- Restricted RAC Point-Set Embeddings
- Restricted RAC1 Point-Set Embeddings
- Restricted RAC2 Point-Set Embeddings
- Unrestricted RAC and AC Point-Set Embeddings
- Open Problems
- References
- Drawing Unordered Trees on $ k$-Grids
- Introduction
- Preliminaries
- Complete 7-Ary Trees
- Complete Ternary Trees
- NP-Hardness Results
- Unit Edge Length
- Area
- Conclusion
- References
- Heuristics for the Maximum2-layer RAC Subgraph Problem
- Introduction
- The Maximum 2-layer RAC Subgraph Problem
- Heuristic Approaches
- Experimental Results
- References
- Games and Cryptography
- Nash Equilibria with Minimum Potential in Undirected Broadcast Games
- Introduction
- Definitions
- Upper Bounds of POPoA and POPoS for Broadcast Games
- Metric Closure
- The Proof of Theorem 4
- The Proof of Theorem 3
- Lower Bounds of POPoA and POPoS for Broadcast Games
- References
- Calculating Average Joint Hamming Weight for Minimal Weight Conversion of $ d$ Integers
- Introduction
- Preliminaries
- Definitions
- Minimal Weight Conversion Algorithm
- AJHW Markov Chain
- Results
- Availability of AJHW Markov Chain
- Finiteness of the Number of States in AJHW Markov Chain
- Existence of the Stationary Distribution
- Conclusions
- 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.