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

Front Cover
Springer Science & Business Media, Jul 31, 2006 - Computers - 528 pages

This book presents the refereed proceedings of the 12th Annual International Computing and Combinatorics Conference, COCOON 2006, held in Taipei, Taiwan, August 2006. The book offers 52 revised full papers presented together with abstracts of 2 invited talks. 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, and more.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

The Unpredictable Deviousness of Models
1
Security Issues in Collaborative Computing Abstract of Keynote Talk
2
A Simplicial Approach for Discrete Fixed Point Theorems Extended Abstract
3
On Incentive Compatible Competitive Selection Protocol Extended Abstract
13
Edge Pricing of Multicommodity Networks for Selfish Users with Elastic Demands
23
Aggregating Strategy for Online Auctions
33
On Indecomposability Preserving Elimination Sequences
42
Improved Algorithms for the Minmax Regret 1Median Problem
52
New Runtime Bounds for Vertex Cover Variants
265
A Detachment Algorithm for Inferring a Graph from Path Frequency
274
Probabilistic Analysis and an Approximation Algorithm
284
Complexity and Parameterized Algorithms
299
An Improved Lower Bound and Resource Augmentation Analysis
309
Improved OnLine Broadcast Scheduling with Deadlines
320
A Tight Analysis of MostRequestedFirst for OnDemand Data Broadcast
330
On Lazy Bin Covering and Packing Problems
340

Partitioning a Multiweighted Graph to Connected Subgraphs of Almost Uniform Size
63
Characterizations and Linear Time Recognition of Helly CircularArc Graphs
73
Varieties Generated by Certain Models of Reversible Finite Automata
83
Membership Problem and Effective Closure Properties
94
On the NegationLimited Circuit Complexity of Sorting and Inverting ktonic Sequences
104
Robust Quantum Algorithms with εBiased Oracles
116
The Complexity of BlackBox Ring Problems
126
Lower Bounds and Parameterized Approach for Longest Common Subsequence
136
Finding Patterns with Variable Length Gaps or Dont Cares
146
The Matrix Orthogonal Decomposition Problem in IntensityModulated Radiation Therapy
156
A PolynomialTime Approximation Algorithm for a Geometric Dispersion Problem
166
A PTAS for Cutting Out Polygons with Lines
176
On Unfolding Lattice PolygonsTrees and Diameter4 Trees
186
Restricted Mesh Simplification Using Edge Contractions
196
Enumerating Noncrossing Minimally Rigid Frameworks
205
Sequences Characterizing kTrees
216
On the Threshold of Having a Linear Treewidth in Random Graphs
226
Reconciling Gene Trees with Apparent Polytomies
235
Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem
245
Computing MaximumScoring Segments in Almost Linear Time
255
Creation and Growth of Components in a Random Hypergraph Process
350
Optimal Acyclic Edge Colouring of Grid Like Graphs
360
An Edge Ordering Problem of Regular Hypergraphs
368
Efficient Partially Blind Signature Scheme with Provable Security
378
A Rigorous Analysis for SetUp Time Models A Metric Perspective
387
Geometric Representation of Graphs in Low Dimension
398
The OnLine Heilbronns Triangle Problem in d Dimensions
408
Counting dDimensional Polycubes and Nonrectangular Planar Polyominoes
418
Approximating MinMax Regret Versions of Some Polynomial Problems
428
The Class Constrained Bin Packing Problem with Applications to VideoonDemand
439
MAXSNP Hardness and Approximation of SelectedInternal Steiner Trees
449
Minimum Clique Partition Problem with Constrained Weight for Interval Graphs
459
OverlapFree Regular Languages
469
On the Combinatorial Representation of Information
479
Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard
489
Bimodal Crossing Minimization
497
Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem
507
On the Effectiveness of the Linear Programming Relaxation of the 01 Multicommodity Minimum Cost Network Flow Problem
517
Author Index
527
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information