Computing and combinatorics : 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005 : proceedings
Author(s)
Bibliographic Information
Computing and combinatorics : 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005 : proceedings
（Lecture notes in computer science, 3595）
Springer, c2005
- Other Title
-
Computing and combinatorics : COCOON 2005
Computing and combinatorics : 11th Annual International Conference, COCOON 2005, Kunming, China, August 2005 : proceedings
Available at / 17 libraries
-
No Libraries matched.
- Remove all filters.
Note
Includes bibliographical references and index
Description and Table of Contents
Description
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.
Table of Contents
Invited Lectures.- Completeness for Parity Problems.- Monotony and Surprise.- Smoothed Analysis of Algorithms and Heuristics.- Bioinformatics.- Gene Network: Model, Dynamics and Simulation.- Conserved Interval Distance Computation Between Non-trivial Genomes.- RNA Multiple Structural Alignment with Longest Common Subsequences.- Perfect Sorting by Reversals.- Genome Rearrangements with Partially Ordered Chromosomes.- Quartet-Based Phylogeny Reconstruction from Gene Orders.- Algorithmic and Complexity Issues of Three Clustering Methods in Microarray Data Analysis.- RIATA-HGT: A Fast and Accurate Heuristic for Reconstructing Horizontal Gene Transfer.- A New Pseudoknots Folding Algorithm for RNA Structure Prediction.- Rapid Homology Search with Two-Stage Extension and Daughter Seeds.- On the Approximation of Computing Evolutionary Trees.- Networks.- Theoretically Good Distributed CDMA/OVSF Code Assignment for Wireless Ad Hoc Networks.- Improved Approximation Algorithms for the Capacitated Multicast Routing Problem.- Construction of Scale-Free Networks with Partial Information.- Radio Networks with Reliable Communication.- Geometric Network Design with Selfish Agents.- Bicriteria Network Design via Iterative Rounding.- Interference in Cellular Networks: The Minimum Membership Set Cover Problem.- Routing and Coloring for Maximal Number of Trees.- Share the Multicast Payment Fairly.- On Packing and Coloring Hyperedges in a Cycle.- Fault-Tolerant Relay Node Placement in Wireless Sensor Networks.- String Algorithms.- Best Fitting Fixed-Length Substring Patterns for a Set of Strings.- String Coding of Trees with Locality and Heritability.- Finding Longest Increasing and Common Subsequences in Streaming Data.- O(n 2 log n) Time On-Line Construction of Two-Dimensional Suffix Trees.- Scheduling.- Min-Energy Voltage Allocation for Tree-Structured Tasks.- Semi-online Problems on Identical Machines with Inexact Partial Information.- On-Line Simultaneous Maximization of the Size and the Weight for Degradable Intervals Schedules.- Off-Line Algorithms for Minimizing Total Flow Time in Broadcast Scheduling.- Complexity.- Oblivious and Adaptive Strategies for the Majority and Plurality Problems.- A Note on Zero Error Algorithms Having Oracle Access to One NP Query.- On the Complexity of Computing the Logarithm and Square Root Functions on a Complex Domain.- Solovay Reducibility on D-c.e Real Numbers.- Steiner Trees.- Algorithms for Terminal Steiner Trees.- Simple Distributed Algorithms for Approximating Minimum Steiner Trees.- A Truthful (2-2/k)-Approximation Mechanism for the Steiner Tree Problem with k Terminals.- Graph Drawing and Layout Design.- Radial Coordinate Assignment for Level Graphs.- A Theoretical Upper Bound for IP-Based Floorplanning.- Quantum Computing.- Quantum Noisy Rational Function Reconstruction.- Promised and Distributed Quantum Search.- Randomized Algorithms.- Efficient and Simple Generation of Random Simple Connected Graphs with Prescribed Degree Sequence.- Randomized Quicksort and the Entropy of the Random Source.- Subquadratic Algorithm for Dynamic Shortest Distances.- Randomly Generating Triangulations of a Simple Polygon.- Geometry.- Triangulating a Convex Polygon with Small Number of Non-standard Bars.- A PTAS for a Disc Covering Problem Using Width-Bounded Separators.- Efficient Algorithms for Intensity Map Splitting Problems in Radiation Therapy.- Distributions of Points in d Dimensions and Large k-Point Simplices.- Exploring Simple Grid Polygons.- Approximation Algorithms for Cutting Out Polygons with Lines and Rays.- Efficient Non-intersection Queries on Aggregated Geometric Data.- An Upper Bound on the Number of Rectangulations of a Point Set.- Codes.- Opportunistic Data Structures for Range Queries.- Generating Combinations by Prefix Shifts.- Error-Set Codes and Related Objects.- Finance.- On Walrasian Price of CPU Time.- On-Line Algorithms for Market Equilibria.- Interval Subset Sum and Uniform-Price Auction Clearing.- Facility Location.- Improved Algorithms for the K-Maximum Subarray Problem for Small K.- Server Allocation Algorithms for Tiered Systems.- An Improved Approximation Algorithm for Uncapacitated Facility Location Problem with Penalties.- The Reverse Greedy Algorithm for the Metric K-Median Problem.- On Approximate Balanced Bi-clustering.- Graph Theory.- Toroidal Grids Are Anti-magic.- Optimally Balanced Forward Degree Sequence.- Conditionally Critical Indecomposable Graphs.- Graph Algorithms.- A Tight Analysis of the Maximal Matching Heuristic.- New Streaming Algorithms for Counting Triangles in Graphs.- A New Approach and Faster Exact Methods for the Maximum Common Subgraph Problem.- On the Power of Lookahead in On-Line Vehicle Routing Problems.- Efficient Algorithms for Simplifying Flow Networks.- Approximation Algorithms for the b-Edge Dominating Set Problem and Its Related Problems.- Bounded Degree Closest k-Tree Power Is NP-Complete.- A New Algorithm for the Hypergraph Transversal Problem.- On Finding a Shortest Path in Circulant Graphs with Two Jumps.- A Linear Time Algorithm for Finding a Maximal Planar Subgraph Based on PC-Trees.- Algorithms for Finding Distance-Edge-Colorings of Graphs.- On the Recognition of Probe Graphs of Some Self-Complementary Classes of Perfect Graphs.- Power Domination Problem in Graphs.- Complexity and Approximation of Satisfactory Partition Problems.- Distributed Weighted Vertex Cover via Maximal Matchings.- On the Complexity of the Balanced Vertex Ordering Problem.- An O(2 O(k) n 3) FPT Algorithm for the Undirected Feedback Vertex Set Problem.- Approximating the Longest Cycle Problem on Graphs with Bounded Degree.- Others.- Bin Packing and Covering Problems with Rejection.- Query-Monotonic Turing Reductions.- On Sequential and 1-Deterministic P Systems.- Global Optimality Conditions and Near-Perfect Optimization in Coding.- Angel, Devil, and King.- Overlaps Help: Improved Bounds for Group Testing with Interval Queries.- New Efficient Simple Authenticated Key Agreement Protocol.- A Quadratic Lower Bound for Rocchio's Similarity-Based Relevance Feedback Algorithm.- The Money Changing Problem Revisited: Computing the Frobenius Number in Time O(ka 1).- W-Hardness Under Linear FPT-Reductions: Structural Properties and Further Applications.- Some New Results on Inverse Sorting Problems.
by "Nielsen BookData"