WALCOM: Algorithms and Computation: Second International Workshop, WALCOM 2008, Dhaka, Bangladesh, February 7-8, 2008. Proceedings

Satoshi Fujita (auth.), Shin-ichi Nakano, Md. Saidur Rahman (eds.)354077890X, 9783540778905

This book constitutes the refereed proceedings of the Second International Workshop on Algorithms and Computation, WALCOM 2008, held in Dhaka, Bangladesh, in February 2008.

The 19 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 57 submissions. The papers feature original research in the areas of algorithms and data structures, combinatorial algorithms, graph drawings and graph algorithms, parallel and distributed algorithms, string algorithms, computational geometry, graphs in bioinformatics and computational biology. The papers are organized in topical sections on bioinformatics algorithms, computational geometry and graph drawing, graph algorithms, and algorithm engineering.

Table of contents :
Front Matter….Pages –
Vertex Domination in Dynamic Networks….Pages 1-12
Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis….Pages 13-24
Simple Geometrical Intersection Graphs….Pages 25-33
On the Approximability of Comparing Genomes with Duplicates….Pages 34-45
Indexing Circular Patterns….Pages 46-57
A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs….Pages 58-69
Cover Ratio of Absolute Neighbor….Pages 70-80
Computing β -Drawings of 2-Outerplane Graphs in Linear Time….Pages 81-87
Upward Drawings of Trees on the Minimum Number of Layers….Pages 88-99
Guarding Exterior Region of a Simple Polygon….Pages 100-110
Computing Nice Projections of Convex Polyhedra….Pages 111-119
A Compact Encoding of Plane Triangulations with Efficient Query Supports….Pages 120-131
Four-Connected Spanning Subgraphs of Doughnut Graphs….Pages 132-143
Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs….Pages 144-156
Linear-Time 3-Approximation Algorithm for the r -Star Covering Problem….Pages 157-168
Multi-commodity Source Location Problems and Price of Greed….Pages 169-179
Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs….Pages 180-187
Optimal Algorithms for Detecting Network Stability….Pages 188-199
On Certain New Models for Paging with Locality of Reference….Pages 200-209
Listing All Plane Graphs….Pages 210-221
Pairwise Compatibility Graphs….Pages 222-233
Multilevel Bandwidth and Radio Labelings of Graphs….Pages 234-239
Back Matter….Pages –