Inhalt
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.