WALCOM: Algorithm and Computation
6th International Workshop, WALCOM 2012, Dhaka, Bangladesh, February 15-17, 2012. Proceedings
Published on 27. February 2012
XV, 241 pages
978-3-642-28076-4 (ISBN)
Description
This book constitutes the refereed proceedings of the 6th International Workshop on Algorithms and Computation, WALCOM 2012, held in Dhaka, Bangladesh, in February 2012. The 20 full papers presented together with 3 invited papers were carefully reviewed and selected from 50 submissions. The papers are grouped in topical sections on graph algorithms; computational geometry; approximation algorithms; graph drawing; string and data structures; and games and cryptography.
More details
Other editions
Additional editions
Md. Saidur Rahman | Shin-ichi Nakano
WALCOM: Algorithm and Computation
6th International Workshop, WALCOM 2012, Dhaka, Bangladesh, February 15-17, 2012. Proceedings
Book
01/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
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
