Leslie G. Valiant (auth.), Lusheng Wang (eds.)3540280618, 9783540280613
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.
Table of contents :
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 –
Reviews
There are no reviews yet.