the proceedings contain 38 papers from the algorithms and datastructures: 9thinternationalworkshop, wads 2005. the topics discussed include: towards a theory of algorithms;heap building bounds;parameterized complex...
详细信息
the proceedings contain 38 papers from the algorithms and datastructures: 9thinternationalworkshop, wads 2005. the topics discussed include: towards a theory of algorithms;heap building bounds;parameterized complexity of generalized vertex cover problems;the complexity of implicit and space efficient priority queues;analysis of a class of tries with adaptive multi-digit branching;balanced aspect ratio trees revisited;improved combinatorial group testing for real-world problem sizes;approximating the online set multicover problems via randomized winnowing;succinct representation of triangulations with a boundary;line-segment intersection made in-place;improved fixed-parameter algorithms for two feedback set problems;and dynamic hotlinks.
Given a forest F = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E9; such that in the augmented graph H = (V, E boolean OR E9;) any pair of vertices can be con...
详细信息
Given a forest F = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E' such that in the augmented graph H = (V, E boolean OR E') any pair of vertices can be connected by two vertex-disjoint paths of length <= D. We show that this problem and some of its variants are NP-hard, and we present approximation algorithms with worst-case bounds 6 and 4. these algorithms can be implemented in O(vertical bar V vertical bar log vertical bar V vertical bar a) time. (c) 2008 Elsevier B.V. All rights reserved.
It is shown that for any orthogonal subdivision of size n in a d-dimensional Euclidean space, d ∈ , d ≥ 2, there is an axis-parallel line that stabs at least Ω(log1/(d-1) n) boxes. For any integer k, 1 ≤ k 1/[(d-1...
详细信息
the restricted rotation distance d(R)(S, T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T, where rotations take place at the root of S, or at the right child of t...
详细信息
the restricted rotation distance d(R)(S, T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T, where rotations take place at the root of S, or at the right child of the root. A sharp upper bound d(R) (S, T) <= 4n - 8 is known, based on group theory [S. Cleary, J. Taback., Bounding restricted rotation distance, Information Processing Letters 88 (5) (2003) 251-256]. We refine this bound to a sharp d(R) (S, T) <= 4n - 8 - rho(S) - rho(T), where rho(S) and rho(T) are the numbers of vertices in the rightmost vertex chains of the two trees, using an elementary transformation algorithm. We then generalize the concept to k-restricted rotation, by allowing rotations to take place at all the vertices of the highest k levels of the tree, and study the new distance for k = 2. the case k >= 3 is essentially open. (c) 2006 Elsevier B.V. All rights reserved.
Let S be a set of n moving points in the plane, We present a kinetic and dynamic (randomized) data structure for maintaining the convex hull of S. the structure uses O(n) space, and processes an expected number of O(n...
详细信息
ISBN:
(纸本)3540281010
Let S be a set of n moving points in the plane, We present a kinetic and dynamic (randomized) data structure for maintaining the convex hull of S. the structure uses O(n) space, and processes an expected number of O(n(2)beta(s+2) (n) log n) critical events, each in O(log (2)n) expected time, including O(n) insertions, deletions, and changes in the flight plans of the points, Here s is the maximum number of times where any specific triple of points can become collinear, beta(s)(q) = lambda(s)(q)/q, and lambda(s)(q) is the maximum length of Davenport-Schinzel sequences of order s on n symbols. Compared withthe previous solution of Basch et al. [2], our structure uses simpler certificates, uses roughly the same resources, and is also dynamic.
Given a forest F = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E9; such that in the augmented graph H = (V, E boolean OR E9;) any pair of vertices can be con...
详细信息
ISBN:
(纸本)3540281010
Given a forest F = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E' such that in the augmented graph H = (V, E boolean OR E') any pair of vertices can be connected by two vertex-disjoint paths of length <= D. We show that this problem and some of its variants are NP-hard, and we present approximation algorithms with worst-case bounds 6 and 4. these algorithms can be implemented in O(vertical bar V vertical bar log vertical bar V vertical bar a) time. (c) 2008 Elsevier B.V. All rights reserved.
We consider the problem of designing succinct geometric datastructures while maintaining efficient navigation operations. A data structure is said succinct if the asymptotic amount of space it uses matches the entrop...
详细信息
In recent years, there has been an explosion of interest in succinct datastructures, which store the given data in compact or compressed formats and answer queries on the data rapidly while it is still in its compres...
详细信息
the proceedings contain 41 papers from the Approximation, Randomization and Combinatorial Optimization - algorithms and Techniques: 8thinternationalworkshop on Approximation algorithms for Combinatorial Optimization...
详细信息
the proceedings contain 41 papers from the Approximation, Randomization and Combinatorial Optimization - algorithms and Techniques: 8thinternationalworkshop on Approximation algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9thinternationalworkshop on Randomization and Computation, RANDOM 2005, Proceedings. the topics discussed include: a rounding algorithm for approximating minimum Manhattan networks;packing element-disjoint steiner trees;finding graph matchings in data streams;efficient approximation of convex recolorings;sampling bounds for stochastic optimization;the online clique avoidance game on random graphs;mixing points on a circle;and reconstructive dispensers and hitting set generators.
暂无评论