We study a space-efficient algorithm for computing a centerpoint for a set P of n points in R-2, where the points in P are given in a read-only array. We propose an algorithm that finds a centerpoint of P in O (T (n(2...
详细信息
We study a space-efficient algorithm for computing a centerpoint for a set P of n points in R-2, where the points in P are given in a read-only array. We propose an algorithm that finds a centerpoint of P in O (T (n(2)) log(3) n) time using O (S(n(2))) extra space, where T(n) and S(n) are the time and extra space complexities of computing the median among a set of n elements stored in a read-only array. We also present the applications of this algorithm for computing the Tukey depth and k-hull of a point set in R-2. (c) 2015 Elsevier B.V. All rights reserved.
Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O mml:mfenced close=")" open="("nlogntime and space. O...
详细信息
Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O mml:mfenced close=")" open="("nlogntime and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n <= s <= n we present algorithms that use O mml:mfenced close=")" open="("slogn bits and Oalgorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.
The degeneracy of a graph G is defined as the smallest value k such that every subgraph of G has a vertex with a degree of at most k. Given a graph G, its degeneracy can be easily calculated provided sufficient memory...
详细信息
The degeneracy of a graph G is defined as the smallest value k such that every subgraph of G has a vertex with a degree of at most k. Given a graph G, its degeneracy can be easily calculated provided sufficient memory is available. In this paper, we focus on scenarios where only o(n) bits of additional read-write memory are available, apart from the input stored in read-only memory. Within this context, we introduce two FPT algorithms for degeneracy, parameterized by neighborhood diversity and the cluster vertex deletion number.
Let n be the size of a parameterized problem and k the parameter. We present kernels for Feedback Vertex Set and Path Contraction whose sizes are all polynomial in k and that are computable in polynomial time and with...
详细信息
ISBN:
(纸本)9789819723393;9789819723409
Let n be the size of a parameterized problem and k the parameter. We present kernels for Feedback Vertex Set and Path Contraction whose sizes are all polynomial in k and that are computable in polynomial time and with O(poly(k) log n) bits (of working memory). By using kernel cascades, we obtain the best known kernels in polynomial time with O(poly(k) log n) bits.
We present the first o(n)-space polynomial-time algorithm for computing the length of a longest common subsequence. Given two strings of length n, the algorithm runs in O(n(3)) time with O (n log(1.5) n/2(root logn) b...
详细信息
We present the first o(n)-space polynomial-time algorithm for computing the length of a longest common subsequence. Given two strings of length n, the algorithm runs in O(n(3)) time with O (n log(1.5) n/2(root logn) bits of space. (C) 2021 Elsevier B.V. All rights reserved.
This paper presents an algorithm for rotating a subimage in place without using any extra working array. Due to this constraint, we have to overwrite pixel values by interpolated values. Key ideas are local reliabilit...
详细信息
This paper presents an algorithm for rotating a subimage in place without using any extra working array. Due to this constraint, we have to overwrite pixel values by interpolated values. Key ideas are local reliability test which determines whether interpolation at a pixel is carried out correctly without using interpolated values, and lazy interpolation which stores interpolated values in a region which is never used for output images and then fills in interpolated values after safety is guaranteed. It is shown that linear interpolation is always safely implemented. An extension to cubic interpolation is also discussed.
Asano et al. [JoCG 2011] proposed an open problem of computing the minimum enclosing circle of a set of n points in 2 given in a read-only array in sub-quadratic time. We show that Megiddo's prune and search algor...
详细信息
We present space-efficient algorithms for computing the convex hull of a simple polygonal line in-place, in linear time. It turns out that the problem is as hard as in-place stable partition, i.e., if there were a tru...
详细信息
We present space-efficient algorithms for computing the convex hull of a simple polygonal line in-place, in linear time. It turns out that the problem is as hard as in-place stable partition, i.e., if there were a truly simple solution then in-place stable partition would also have a truly simple solution, and vice versa. Nevertheless, we present a simple self-contained solution that uses O(log n) space, and indicate how to improve it to O(1) space with the same techniques used for stable partition. If the points inside the convex hull can be discarded, then there is a truly simple solution that uses a single call to stable partition, and even that call can be spared if only extreme points are desired (and not their order). If the polygonal line is closed, the problem admits a very simple solution which does not call for stable partitioning at all. (c) 2005 Elsevier B.V. All rights reserved.
暂无评论