Computing and Combinatorics: 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005. Proceedings

Front Matter....Pages -
Completeness for Parity Problems....Pages 1-8
Monotony and Surprise....Pages 9-9
Smoothed Analysis of Algorithms and Heuristics....Pages 10-11
Gene Network: Model, Dynamics and Simulation....Pages 12-21
Conserved Interval Distance Computation Between Non-trivial Genomes....Pages 22-31
RNA Multiple Structural Alignment with Longest Common Subsequences....Pages 32-41
Perfect Sorting by Reversals....Pages 42-51
Genome Rearrangements with Partially Ordered Chromosomes....Pages 52-62
Quartet-Based Phylogeny Reconstruction from Gene Orders....Pages 63-73
Algorithmic and Complexity Issues of Three Clustering Methods in Microarray Data Analysis....Pages 74-83
RIATA-HGT: A Fast and Accurate Heuristic for Reconstructing Horizontal Gene Transfer....Pages 84-93
A New Pseudoknots Folding Algorithm for RNA Structure Prediction....Pages 94-103
Rapid Homology Search with Two-Stage Extension and Daughter Seeds....Pages 104-114
On the Approximation of Computing Evolutionary Trees....Pages 115-125
Theoretically Good Distributed CDMA/OVSF Code Assignment for Wireless Ad Hoc Networks....Pages 126-135
Improved Approximation Algorithms for the Capacitated Multicast Routing Problem....Pages 136-145
Construction of Scale-Free Networks with Partial Information....Pages 146-155
Radio Networks with Reliable Communication....Pages 156-166
Geometric Network Design with Selfish Agents....Pages 167-178
Bicriteria Network Design via Iterative Rounding....Pages 179-187
Interference in Cellular Networks: The Minimum Membership Set Cover Problem....Pages 188-198
Routing and Coloring for Maximal Number of Trees....Pages 199-209
Share the Multicast Payment Fairly....Pages 210-219
On Packing and Coloring Hyperedges in a Cycle....Pages 220-229
Fault-Tolerant Relay Node Placement in Wireless Sensor Networks....Pages 230-239
Best Fitting Fixed-Length Substring Patterns for a Set of Strings....Pages 240-250
String Coding of Trees with Locality and Heritability....Pages 251-262
Finding Longest Increasing and Common Subsequences in Streaming Data....Pages 263-272
 O ( n 2 log n ) Time On-Line Construction of Two-Dimensional Suffix Trees....Pages 273-282
Min-Energy Voltage Allocation for Tree-Structured Tasks....Pages 283-296
Semi-online Problems on Identical Machines with Inexact Partial Information....Pages 297-307
On-Line Simultaneous Maximization of the Size and the Weight for Degradable Intervals Schedules....Pages 308-317
Off-Line Algorithms for Minimizing Total Flow Time in Broadcast Scheduling....Pages 318-328
Oblivious and Adaptive Strategies for the Majority and Plurality Problems....Pages 329-338
A Note on Zero Error Algorithms Having Oracle Access to One NP Query....Pages 339-348
On the Complexity of Computing the Logarithm and Square Root Functions on a Complex Domain....Pages 349-358
Solovay Reducibility on D-c.e Real Numbers....Pages 359-368
Algorithms for Terminal Steiner Trees....Pages 369-379
Simple Distributed Algorithms for Approximating Minimum Steiner Trees....Pages 380-389
A Truthful (2–2/ k )-Approximation Mechanism for the Steiner Tree Problem with k Terminals....Pages 390-400
Radial Coordinate Assignment for Level Graphs....Pages 401-410
A Theoretical Upper Bound for IP-Based Floorplanning....Pages 411-419
Quantum Noisy Rational Function Reconstruction....Pages 420-429
Promised and Distributed Quantum Search....Pages 430-439
Efficient and Simple Generation of Random Simple Connected Graphs with Prescribed Degree Sequence....Pages 440-449
Randomized Quicksort and the Entropy of the Random Source....Pages 450-460
Subquadratic Algorithm for Dynamic Shortest Distances....Pages 461-470
Randomly Generating Triangulations of a Simple Polygon....Pages 471-480
Triangulating a Convex Polygon with Small Number of Non-standard Bars....Pages 481-489
A PTAS for a Disc Covering Problem Using Width-Bounded Separators....Pages 490-503
Efficient Algorithms for Intensity Map Splitting Problems in Radiation Therapy....Pages 504-513
Distributions of Points in d Dimensions and Large k -Point Simplices....Pages 514-523
Exploring Simple Grid Polygons....Pages 524-533
Approximation Algorithms for Cutting Out Polygons with Lines and Rays....Pages 534-543
Efficient Non-intersection Queries on Aggregated Geometric Data....Pages 544-553
An Upper Bound on the Number of Rectangulations of a Point Set....Pages 554-559
Opportunistic Data Structures for Range Queries....Pages 560-569
Generating Combinations by Prefix Shifts....Pages 570-576
Error-Set Codes and Related Objects....Pages 577-585
On Walrasian Price of CPU Time....Pages 586-595
On-Line Algorithms for Market Equilibria....Pages 596-607
Interval Subset Sum and Uniform-Price Auction Clearing....Pages 608-620
Improved Algorithms for the K -Maximum Subarray Problem for Small K ....Pages 621-631
Server Allocation Algorithms for Tiered Systems....Pages 632-643
An Improved Approximation Algorithm for Uncapacitated Facility Location Problem with Penalties....Pages 644-653
The Reverse Greedy Algorithm for the Metric K -Median Problem....Pages 654-660
On Approximate Balanced Bi-clustering....Pages 661-670
Toroidal Grids Are Anti-magic....Pages 671-679
Optimally Balanced Forward Degree Sequence....Pages 680-689
Conditionally Critical Indecomposable Graphs....Pages 690-700
A Tight Analysis of the Maximal Matching Heuristic....Pages 701-709
New Streaming Algorithms for Counting Triangles in Graphs....Pages 710-716
A New Approach and Faster Exact Methods for the Maximum Common Subgraph Problem....Pages 717-727
On the Power of Lookahead in On-Line Vehicle Routing Problems....Pages 728-736
Efficient Algorithms for Simplifying Flow Networks....Pages 737-746
Approximation Algorithms for the b -Edge Dominating Set Problem and Its Related Problems....Pages 747-756
Bounded Degree Closest k -Tree Power Is NP-Complete....Pages 757-766
A New Algorithm for the Hypergraph Transversal Problem....Pages 767-776
On Finding a Shortest Path in Circulant Graphs with Two Jumps....Pages 777-786
A Linear Time Algorithm for Finding a Maximal Planar Subgraph Based on PC-Trees....Pages 787-797
Algorithms for Finding Distance-Edge-Colorings of Graphs....Pages 798-807
On the Recognition of Probe Graphs of Some Self-Complementary Classes of Perfect Graphs....Pages 808-817
Power Domination Problem in Graphs....Pages 818-828
Complexity and Approximation of Satisfactory Partition Problems....Pages 829-838
Distributed Weighted Vertex Cover via Maximal Matchings....Pages 839-848
On the Complexity of the Balanced Vertex Ordering Problem....Pages 849-858
An O (2 O(k) n 3 ) FPT Algorithm for the Undirected Feedback Vertex Set Problem....Pages 859-869
Approximating the Longest Cycle Problem on Graphs with Bounded Degree....Pages 870-884
Bin Packing and Covering Problems with Rejection....Pages 885-894
Query-Monotonic Turing Reductions....Pages 895-904
On Sequential and 1-Deterministic P Systems....Pages 905-914
Global Optimality Conditions and Near-Perfect Optimization in Coding....Pages 915-924
Angel, Devil, and King....Pages 925-934
Overlaps Help: Improved Bounds for Group Testing with Interval Queries....Pages 935-944
New Efficient Simple Authenticated Key Agreement Protocol....Pages 945-954
A Quadratic Lower Bound for Rocchio’s Similarity-Based Relevance Feedback Algorithm....Pages 955-964
The Money Changing Problem Revisited: Computing the Frobenius Number in Time O ( ka 1 )....Pages 965-974
 W -Hardness Under Linear FPT-Reductions: Structural Properties and Further Applications....Pages 975-984
Some New Results on Inverse Sorting Problems....Pages 985-992
Back Matter....Pages -