Computing and Combinatorics 2005

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.