This book constitutes the proceedings of the 4th International Workshop on Algorithms and Computation, held in Dhaka, Bangladesh, in February 2010.
The 23 revised full papers were carefully reviewed and selected from 60 submissions. The volume also contains 4 invited papers.The topics covered are graph drawing, computational geometry, graph algorithms, computational biology and strings, combinatorial optimization, approximation algorithms, and parameterized complexity.
Author(s): Jacob Fox, Fabrizio Frati, János Pach, Rom Pinchasi (auth.), Md. Saidur Rahman, Satoshi Fujita (eds.)
Series: Lecture Notes in Computer Science 5942 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 305
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Math Applications in Computer Science; Symbolic and Algebraic Manipulation; Computational Biology/Bioinformatics; Algorithms
Front Matter....Pages -
Crossings between Curves with Many Tangencies....Pages 1-8
Constant-Work-Space Algorithm for a Shortest Path in a Simple Polygon....Pages 9-20
Approximation Algorithms for Art Gallery Problems in Polygons and Terrains....Pages 21-34
The Hamiltonian Augmentation Problem and Its Applications to Graph Drawing....Pages 35-46
Small Grid Drawings of Planar Graphs with Balanced Bipartition....Pages 47-57
Switch-Regular Upward Planar Embeddings of Trees....Pages 58-69
A Global k -Level Crossing Reduction Algorithm....Pages 70-81
Computation of Non-dominated Points Using Compact Voronoi Diagrams....Pages 82-93
Cutting a Convex Polyhedron Out of a Sphere....Pages 94-101
A Simple Algorithm for Approximate Partial Point Set Pattern Matching under Rigid Motion....Pages 102-112
Acyclically 3-Colorable Planar Graphs....Pages 113-124
Reconstruction Algorithm for Permutation Graphs....Pages 125-135
Harmonious Coloring on Subclasses of Colinear Graphs....Pages 136-148
Comparing RNA Structures with Biologically Relevant Operations Cannot Be Done without Strong Combinatorial Restrictions....Pages 149-160
The 1.375 Approximation Algorithm for Sorting by Transpositions Can Run in O ( n log n ) Time....Pages 161-166
Parallel Algorithms for Encoding and Decoding Blob Code....Pages 167-178
A Rooted-Forest Partition with Uniform Vertex Demand....Pages 179-190
A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique....Pages 191-203
On Some Simple Widths....Pages 204-215
A New Model for a Scale-Free Hierarchical Structure of Isolated Cliques....Pages 216-227
The Covert Set-Cover Problem with Application to Network Discovery....Pages 228-239
Variants of Spreading Messages....Pages 240-251
On Finding a Better Position of a Convex Polygon Inside a Circle to Minimize the Cutting Cost....Pages 252-262
Real Root Isolation of Multi-Exponential Polynomials with Application....Pages 263-268
FPT Algorithms for Connected Feedback Vertex Set....Pages 269-280
A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs....Pages 281-292
Pathwidth and Searching in Parameterized Threshold Graphs....Pages 293-304
Back Matter....Pages -
