## Computing and Combinatorics: 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-19, 2005, ProceedingsThe refereed proceedings of the 11th Annual International Computing and Combinatorics Conference, COCOON 2005, held in Kunming, China in August 2005. The 96 revised full papers presented together with abstracts of 3 invited talks were carefully reviewed and selected from 353 submissions. The papers cover most aspects of theoretical computer science and combinatorics related to computing and are organized in topical sections on bioinformatics, networks, string algorithms, scheduling, complexity, steiner trees, graph drawing and layout design, quantum computing, randomized algorithms, geometry, codes, finance, facility location, graph theory, graph algorithms. |

### What people are saying - Write a review

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

### Contents

1 | |

22 | |

Perfect Sorting by Reversals | 42 |

QuartetBased Phylogeny Reconstruction from Gene Orders | 63 |

A Fast and Accurate Heuristic | 84 |

Rapid Homology Search with TwoStage Extension and Daughter Seeds | 104 |

On the Approximation of Computing Evolutionary Trees | 115 |

Improved Approximation Algorithms | 136 |

Efficient Nonintersection Queries on Aggregated Geometric Data | 544 |

An Upper Bound on the Number of Rectangulations of a Point Set | 554 |

Codes | 560 |

Generating Combinations by Prefix Shifts | 570 |

ErrorSet Codes and Related Objects | 577 |

Finance | 586 |

OnLine Algorithms for Market Equilibria | 596 |

Interval Subset Sum and UniformPrice Auction Clearing | 608 |

Radio Networks with Reliable Communication | 156 |

Bicriteria Network Design via Iterative Rounding | 179 |

Routing and Coloring for Maximal Number of Trees | 199 |

On Packing and Coloring Hyperedges in a Cycle | 220 |

String Algorithms | 240 |

Finding Longest Increasing and Common Subsequences | 263 |

Scheduling | 283 |

Semionline Problems on Identical Machines | 297 |

OffLine Algorithms for Minimizing Total Flow Time | 318 |

A Note on Zero Error Algorithms Having Oracle Access | 339 |

Solovay Reducibility on Dc e Real Numbers | 359 |

Fábio Viduani Martinez José Coelho de Pina and José Soares | 372 |

Simple Distributed Algorithms | 380 |

Graph Drawing and Layout Design | 401 |

Quantum Computing | 420 |

Randomized Algorithms | 440 |

Subquadratic Algorithm for Dynamic Shortest Distances | 461 |

Triangulating a Convex Polygon with Small Number | 481 |

Efficient Algorithms for Intensity Map Splitting Problems | 504 |

Distributions of Points in d Dimensions and Large kPoint Simplices | 514 |

Exploring Simple Grid Polygons | 524 |

Approximation Algorithms for Cutting Out Polygons | 534 |

Facility Location | 621 |

Server Allocation Algorithms for Tiered Systems | 632 |

The Reverse Greedy Algorithm for the Metric KMedian Problem | 654 |

Toroidal Grids Are Antimagic | 671 |

Conditionally Critical Indecomposable Graphs | 690 |

New Streaming Algorithms for Counting Triangles in Graphs | 710 |

On the Power of Lookahead in OnLine Vehicle Routing Problems | 728 |

Approximation Algorithms for the bEdge Dominating Set Problem | 747 |

Bounded Degree Closest kTree Power Is NPComplete | 757 |

On Finding a Shortest Path in Circulant Graphs with Two Jumps | 777 |

Algorithms for Finding DistanceEdgeColorings of Graphs | 798 |

Power Domination Problem in Graphs | 818 |

Distributed Weighted Vertex Cover via Maximal Matchings | 839 |

An O2Okn3 FPT Algorithm | 859 |

Others | 885 |

QueryMonotonic Turing Reductions | 895 |

Global Optimality Conditions and NearPerfect Optimization in Coding | 915 |

Improved Bounds for Group Testing | 935 |

A Quadratic Lower Bound for Rocchios SimilarityBased Relevance | 955 |

993 | |

### Other editions - View all

Computing and Combinatorics: 11th Annual International Conference, COCOON ... Lusheng Wang No preview available - 2005 |

### Common terms and phrases

apply approximation algorithm assignment assume Berlin Heidelberg 2005 circulant graph cograph colors competitive ratio complexity component Computer Science connected consider constant construction contains corresponding cost cycle defined degree distribution denote edge exists function gene genome given graph G heuristic hyperedge hypergraph input integer interval iteration least Lemma length Let G linear LNCS lower bound matrix matroid maximal maximum minimal minimum module multicast NP-complete NP-hard O(log obtain on-line optimal solution output pair paper partition permutation planar planar graphs polygon polynomial polynomial-time prefix sums Proc Proof protocol pseudoknots query random reduce resp satisfies schedule Section segment shortest path solve Springer-Verlag Berlin Heidelberg Steiner tree step string structure subgraph subset terminal Theorem triangulation update upper bound vector vertex cover vertex cover problem vertex set vertices Walrasian Equilibrium Wang weight