Computing and Combinatorics: 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006. Proceedings

Franco P. Preparata (auth.), Danny Z. Chen, D. T. Lee (eds.)3540369252, 9783540369257

This book presents the refereed proceedings of the 12th Annual International Computing and Combinatorics Conference, COCOON 2006, held in Taipei, Taiwan, in August 2006.

The 52 revised full papers presented together with abstracts of 2 invited talks were carefully reviewed and selected from 137 submissions. The papers are organized in topical sections on computational economics, finance, and management, graph algorithms, computational complexity and computability, quantum computing, computational biology and medicine, computational geometry, graph theory, computational biology, graph algorithms and applications, on-line algorithms, algorithms for security and systems, discrete geometry and graph theory, approximation algorithms, and experimental algorithms.

---

Table of contents :
Front Matter….Pages –
The Unpredictable Deviousness of Models….Pages 1-1
Security Issues in Collaborative Computing….Pages 2-2
Robust Quantum Algorithms with ε -Biased Oracles….Pages 116-125
The Complexity of Black-Box Ring Problems….Pages 126-135
Lower Bounds and Parameterized Approach for Longest Common Subsequence….Pages 136-145
Finding Patterns with Variable Length Gaps or Don’t Cares….Pages 146-155
The Matrix Orthogonal Decomposition Problem in Intensity-Modulated Radiation Therapy….Pages 156-165
A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem….Pages 166-175
A PTAS for Cutting Out Polygons with Lines….Pages 176-185
A Simplicial Approach for Discrete Fixed Point Theorems….Pages 3-12
On Incentive Compatible Competitive Selection Protocol….Pages 13-22
Edge Pricing of Multicommodity Networks for Selfish Users with Elastic Demands….Pages 23-32
Aggregating Strategy for Online Auctions….Pages 33-41
On Indecomposability Preserving Elimination Sequences….Pages 42-51
Improved Algorithms for the Minmax Regret 1-Median Problem….Pages 52-62
Partitioning a Multi-weighted Graph to Connected Subgraphs of Almost Uniform Size….Pages 63-72
Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs….Pages 73-82
Varieties Generated by Certain Models of Reversible Finite Automata….Pages 83-93
Iterated TGR Languages: Membership Problem and Effective Closure Properties….Pages 94-103
On the Negation-Limited Circuit Complexity of Sorting and Inverting k -tonic Sequences….Pages 104-115
On Unfolding Lattice Polygons/Trees and Diameter-4 Trees….Pages 186-195
Restricted Mesh Simplification Using Edge Contractions….Pages 196-204
Enumerating Non-crossing Minimally Rigid Frameworks….Pages 205-215
Sequences Characterizing k -Trees….Pages 216-225
On the Threshold of Having a Linear Treewidth in Random Graphs….Pages 226-234
Reconciling Gene Trees with Apparent Polytomies….Pages 235-244
Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem of Genomes….Pages 245-254
Computing Maximum-Scoring Segments in Almost Linear Time….Pages 255-264
Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants….Pages 265-273
A Detachment Algorithm for Inferring a Graph from Path Frequency….Pages 274-283
The d -Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm….Pages 284-298
Reconstructing Evolution of Natural Languages: Complexity and Parameterized Algorithms….Pages 299-308
On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis….Pages 309-319
Improved On-Line Broadcast Scheduling with Deadlines….Pages 320-329
A Tight Analysis of Most-Requested-First for On-Demand Data Broadcast….Pages 330-339
On Lazy Bin Covering and Packing Problems….Pages 340-349
Creation and Growth of Components in a Random Hypergraph Process….Pages 350-359
Optimal Acyclic Edge Colouring of Grid Like Graphs….Pages 360-367
An Edge Ordering Problem of Regular Hypergraphs….Pages 368-377
Efficient Partially Blind Signature Scheme with Provable Security….Pages 378-386
A Rigorous Analysis for Set-Up Time Models – A Metric Perspective….Pages 387-397
Overlap-Free Regular Languages….Pages 469-478
On the Combinatorial Representation of Information….Pages 479-488
Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard….Pages 489-496
Geometric Representation of Graphs in Low Dimension….Pages 398-407
The On-Line Heilbronn’s Triangle Problem in d Dimensions….Pages 408-417
Counting d -Dimensional Polycubes and Nonrectangular Planar Polyominoes….Pages 418-427
Bimodal Crossing Minimization….Pages 497-506
Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem….Pages 507-516
On the Effectiveness of the Linear Programming Relaxation of the 0-1 Multi-commodity Minimum Cost Network Flow Problem….Pages 517-526
Approximating Min-Max (Regret) Versions of Some Polynomial Problems….Pages 428-438
The Class Constrained Bin Packing Problem with Applications to Video-on-Demand….Pages 439-448
MAX-SNP Hardness and Approximation of Selected-Internal Steiner Trees….Pages 449-458
Minimum Clique Partition Problem with Constrained Weight for Interval Graphs….Pages 459-468
Back Matter….Pages –