Computing and Combinatorics: 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-19, 2005, ProceedingsLusheng Wang The papers in this volume were presented at the Eleventh Annual International ComputingandCombinatorics Conference(COCOON2005), heldAugust16-19, 2005, in Kunming, China. The topicscovermost aspects oftheoreticalcomputer science and combinatorics related to computing. Submissionstotheconferencethisyearwereconductedelectronically.Atotal of 353 papers were submitted, of which 96 were accepted. So the competition is very ?erce. The papers were evaluated by an international program committee consisting of Tatsuya Akutsu, Vineet Bafna, Zhi-Zhong Chen, Siu-Wing Cheng, Francis Chin, Sunghee Choi, Bhaskar DasGupta, Qizhi Fang, Martin Farach- Colton, Ra'aele Giancarlo, Mordecai Golin, Peter Hammer, Tsan-sheng Hsu, Sorin C. Istrail, Samir Khuller, Michael A. Langston, Jianping Li, Weifa Liang, GuohuiLin, BernardMans, SatoruMiyano, C.K.Poon, R.Ravi, DavidSanko?, Shang-Hua Teng, H. F. Ting, Seinosuke Toda, Takeshi Tokuyama, Peng-Jun Wan, Lusheng Wang, Todd Wareham, Jinhui Xu, Xizhong Zheng, Kaizhong Zhang and Binhai Zhu. The authors of submitted papers came from more than 25 countries and regions. In addition to the selected papers, the conference also included three invited presentations by Alberto Apostolico, Shang-Hua Teng, and Leslie G. Valiant. This year's Wang Hao Award (for young researchers) was given to the paperApproximatingtheLongestCycle Problem onGraphs with BoundedDegree by Guantao Chen, Zhicheng Gao, Xingxing Yu and Wenan Zang. I would like to thank all the people who made this meeting possible and - joyable: the authors for submitting papers and the programcommittee members andexternalrefereesfor their excellentwork.I wouldalsoliketo thank thethree invited speakers and the local organizers and colleagues for their assistance. |
Contents
Invited Lectures | 1 |
Conserved Interval Distance Computation Between Nontrivial Genomes | 22 |
Perfect Sorting by Reversals | 42 |
QuartetBased Phylogeny Reconstruction from Gene Orders Tao Liu Jijun Tang and Bernard M E Moret | 63 |
A Fast and Accurate Heuristic | 84 |
Rapid Homology Search with TwoStage Extension and Daughter Seeds | 104 |
On the Approximation of Computing Evolutionary Vincent Berry Sylvain Guillemot François Nicolas Trees | 115 |
Networks | 126 |
Randomized Quicksort and the Entropy of the Random Source | 450 |
Subquadratic Algorithm for Dynamic Shortest Distances | 461 |
Randomly Generating Triangulations of a Simple Polygon Q Ding J Qian W Tsang and C Wang | 471 |
Triangulating a Convex Polygon with Small Number | 481 |
A PTAS for a Disc Covering Problem Using WidthBounded Separators | 490 |
Efficient Algorithms for Intensity Map Splitting Problems | 504 |
Exploring Simple Grid Polygons | 524 |
Efficient Nonintersection Queries on Aggregated Geometric Data | 544 |
Improved Approximation Algorithms | 136 |
Construction of ScaleFree Networks with Partial Information | 146 |
Radio Networks with Reliable Communication | 156 |
Geometric Network Design with Selfish Agents | 167 |
Bicriteria Network Design via Iterative Rounding | 179 |
Routing and Coloring for Maximal Number of Trees Xujin Chen Xiaodong Hu and Tianping Shuai | 199 |
Share the Multicast Payment Fairly | 210 |
On Packing and Coloring Hyperedges in a Cycle Jianping Li Kang Li Ken C K Law and Hao Zhao | 220 |
FaultTolerant Relay Node Placement in Wireless Sensor Networks Hai Liu PengJun Wan and Xiaohua Jia | 230 |
String Algorithms | 240 |
String Coding of Trees with Locality and Heritability | 251 |
Finding Longest Increasing and Common Subsequences | 263 |
On2 logn Time OnLine Construction of TwoDimensional Suffix Trees | 273 |
Scheduling | 283 |
Semionline Problems on Identical Machines | 297 |
OnLine Simultaneous Maximization of the Size | 308 |
OffLine Algorithms for Minimizing Total Flow Time | 318 |
Oblivious and Adaptive Strategies for the Majority | 329 |
A Note on Zero Error Algorithms Having Oracle Access | 339 |
On the Complexity of Computing the Logarithm | 349 |
Solovay Reducibility on Dc e Real Robert Rettinger and Xizhong Zheng Numbers | 359 |
Steiner Trees | 369 |
Simple Distributed Algorithms | 380 |
A Truthful 22kApproximation Mechanism | 390 |
Graph Drawing and Layout Design | 401 |
A Theoretical Upper Bound for IPBased Floorplanning | 411 |
Quantum Computing | 420 |
Promised and Distributed Quantum Search | 430 |
Randomized Algorithms | 440 |
Codes | 560 |
ErrorSet Codes and Related Objects | 577 |
OnLine Algorithms for Market Equilibria | 596 |
Facility Location | 621 |
Server Allocation Algorithms for Tiered Systems | 632 |
The Reverse Greedy Algorithm for the Metric KMedian Problem | 654 |
Toroidal Grids Are TaoMing Wang 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 |
in Circulant Alvar Graphs Ibeas with Carmen Two Jumps | 777 |
on PCTrees | 787 |
Algorithms for Finding DistanceEdgeColorings of Graphs | 798 |
On the Recognition of Probe Graphs of Some SelfComplementary Classes | 808 |
Cristina Bazgan Zsolt Tuza and Daniel Vanderpooten | 829 |
Fabrizio Grandoni Jochen Könemann and Alessandro Panconesi | 839 |
Jan Kára Jan Kratochvıl and David R Wood | 849 |
for the Undirected Feedback Vertex Set Problem | 859 |
Approximating the Longest Cycle Problem on Graphs | 870 |
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 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 quartets query random reduce resp satisfies schedule Section segment shortest path solve space 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