Computing and Combinatorics: 11th Annual International Conference, Cocoon 2005, Kunming, China, August 16-19, 2005, Proceedings

ISBN-13: 9783540280613 / Angielski / Miękka / 2005 / 1000 str.

Lusheng Wang

Opis

Constitutes the proceedings of the 11th Annual International Computing and Combinatorics Conference, COCOON 2005, held in Kunming, China in August 2005. This title contains 96 revised papers presented together with abstracts of 3 invited talks which cover various aspects of theoretical computer science and combinatorics related to computing.

Spis treści

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.