检索结果-内蒙古大学图书馆

space-efficient algorithms for reachability in directed geometric graphs

THEORETICAL COMPUTER SCIENCE 2023年第1期961卷

作者： Bhore, Sujoy Jain, Rahul Indian Inst Technol Dept Comp Sci & Engn Mumbai India Fernunivers Hagen Hagen Germany

The problem of graph REACHABILITY is to decide whether there is a path from one vertex to another in a given graph. In this paper, we study the REACHABILITY problem on three distinct graph families - intersection graphs of Jordan regions, unit contact disk graphs (penny graphs), and chordal graphs. For each of these graph families, we present space-efficient algorithms for the REACHABILITY problem. For intersection graphs of Jordan regions, we show how to obtain a "good" vertex separator in a space-efficient manner and use it to solve the REACHABILITY in polynomial time and O(m(1/2) log n) space, where n is the number of Jordan regions, and m is the total number of crossings among the regions. We use a similar approach for chordal graphs and obtain a polynomial time and O(m(1/2) log n) space algorithm, where n and m are the number of vertices and edges, respectively. However, for unit contact disk graphs (penny graphs), we use a more involved technique and obtain a better algorithm. We show that for every epsilon > 0, there exists a polynomial time algorithm that can solve REACHABILITY in an n vertex directed penny graph, using O(n(1/4+epsilon)) space. We note that the method used to solve penny graphs does not extend naturally to the class of geometric intersection graphs that include arbitrary size cliques. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Reachability Geometric intersection graphs space-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

FASTER space-efficient algorithms FOR SUBSET SUM, k-SUM, AND RELATED PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 2018年第5期47卷 1755-1777页

作者： Bansal, Nikhil Garg, Shashwat Nederlof, Jesper Vyas, Nikhil Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 AB Eindhoven Netherlands MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA

We present randomized algorithms that solve subset sum and knapsack instances with n items in O*((20.86n)) time, where the O* (.) notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve binary integer programming on n variables with few constraints in a similar running time. We also show that for any constant k >= 2, random instances of k-sum can be solved using O(n(k-0.5) polylog(n)) time and O(log n) space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(log n) space significantly faster than the trivial O(n(2)) time algorithm if no value occurs too often in the same list.

关键词： space-efficient algorithms k-sum subset sum exact exponential time algorithms fine-grained complexity space-time trade-off exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

space-efficient parallel algorithms for combinatorial search problems

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2015年 76卷 58-65页

作者： Pietracaprina, A. Pucci, G. Silvestri, F. Vandin, F. Univ Padua Dipartimento Ingn Informaz I-35131 Padua Italy Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense M Denmark Brown Univ Dept Comp Sci Providence RI 02912 USA

We present space-efficient parallel strategies for two fundamental combinatorial search problems, namely, backtrack search and branch-and-bound, both involving the visit of an n-node tree of height h under the assumption that a node can be accessed only through its father or its children. For both problems we propose efficient algorithms that run on a p-processor distributed-memory machine. For backtrack search, we give a deterministic algorithm running in 0 (n/p + h logp) time, and a Las Vegas algorithm requiring optimal 0 (n/p + h) time, with high probability. Building on the backtrack search algorithm, we also derive a Las Vegas algorithm for branch-and-bound which runs in 0 ((n/p + h logp log n)h log(2) n) time, with high probability. A remarkable feature of our algorithms is the use of only constant space per processor, which constitutes a significant improvement upon previous algorithms whose space requirements per processor depend on the (possibly huge) tree to be explored. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Combinatorial search problems Distributed algorithms Backtrack search Branch-and-bound space-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

space efficient Separator algorithms for Planar Graphs 14th

Space Efficient Separator Algorithms for Planar Graphs

引用

14th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Watanabe, Osamu Tokyo Inst Technol Tokyo 1528550 Japan

ISBN: (纸本)9783030398811;9783030398804

The Separator Theorem states that any planar graph G with n vertices has a separator of size O(root n), that is, a set S of O(root n) vertices of G such that by removing S, G is split into disconnected subgraphs of almost equal size, say, each having more than n/3 vertices. A separator algorithm is an algorithm that computes a separator for a given planar graph. We consider two algorithms that have been developed recently by the author and his colleagues [4,6] for designing a "sublinear-space" and polynomial-time separator algorithm.

关键词： Separator Theorem space-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

space-efficient geometric divide-and-conquer algorithms

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2007年第3期37卷 209-227页

作者： Bose, Prosenjit Maheshwari, Anil Morin, Pat Morrison, Jason Smid, Michiel Vahrenhold, Jan Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Univ Munster Inst Informat D-48149 Munster Germany

We develop a number of space-efficient tools including an approach to simulate divide-and-conquer space-efficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth smallest element in one dimension from a multidimensional set that is sorted in another dimension. We then apply these tools to solve several geometric problems that have solutions using some form of divide-and-conquer. Specifically, we present a deterministic algorithm running in O(n log n) time using O(1) extra memory given inputs of size n for the closest pair problem and a randomized solution running in O(n log n) expected time and using O(1) extra space for the bichromatic closest pair problem. For the orthogonal line segment intersection problem, we solve the problem in O(n log n + k) time using O(1) extra space where n is the number of horizontal and vertical line segments and k is the number of intersections. (C) 2006 Elsevier B.V. All rights reserved.

关键词： space-efficient algorithms in-place algorithms in situ algorithms

来源：评论

学校读者我要写书评

暂无评论

space-efficient geometric divide-and-conquer algorithms

Space-efficient geometric divide-and-conquer algorithms

引用

20th European Workshop on Computational Geometry

关键词： space-efficient algorithms in-place algorithms in situ algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding an optimal path without growing the tree

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2003年第1期49卷 13-41页

作者： Chen, DZ Daescu, O Hu, XB Xu, JH Univ Notre Dame Dept Comp Sci & Engn Notre Dame IN 46556 USA Univ Texas Dept Comp Sci Richardson TX 75083 USA SUNY Buffalo Dept Comp Sci & Engn Buffalo NY 14260 USA

For problems on computing an optimal path as well as its length in a certain setting, the "standard" approach for finding an actual optimal path is by building (or "growing") a single-source optimal path tree. In this paper, we study a class of optimal path problems with the following phenomenon: The space complexity of the algorithms for reporting the lengths of single-source optimal paths for these problems is asymptotically smaller than the space complexity of the "standard" tree-growing algorithms for finding actual optimal paths. We present a general and efficient algorithmic paradigm for finding an actual optimal path for such problems without having to grow a single-source optimal path tree. Our paradigm is based on the "marriage-before-conquer" strategy, the prune-and-search technique, and a new data structure called clipped trees. The paradigm enables us to compute an actual path for a number of optimal path problems and dynamic programming problems in computational geometry, graph theory, and combinatorial optimization. Our algorithmic solutions improve the space bounds (in certain cases, the time bounds as well) of the previously best known algorithms, and settle some open problems. Our techniques are likely to be applicable to other problems. (C) 2003 Elsevier Inc. All rights reserved.

关键词： computational geometry optimal paths arrangments dynamic programming space-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast BWT in small space by blockwise suffix sorting

引用

THEORETICAL COMPUTER SCIENCE 2007年第3期387卷 249-257页

作者： Karkkainen, Juha Univ Helsinki Dept Comp Sci FI-00014 Helsinki Finland

We present a new space- and time-efficient algorithm for computing the Burrow-Wheeler transform (BWT). For any choice of a parameter upsilon E [3, n(2/3)], the computation of BWT for a text of length n takes O(n log n + vn) worst-case time and O(n log n + root upsilon n) average-case time using O(n log n/root upsilon) bits of space in addition to the text and the BWT. For example, if upsilon = log(2) n, the time is O(n log2 n) in the worst case and O(n log n) on an average with the additional space requirement of O(n) bits. The algorithm is alphabet-independent: it uses only character comparisons, and the complexities do not depend on the alphabet size unless upsilon does. A practical implementation is 2-3 times slower than one of the fastest and most space-efficient previous algorithms while needing only one-third of the main memory. The algorithm is based on suffix arrays, but unlike any other algorithm, it can construct the suffix array a small block at a time without storing the rest of the suffix array anywhere. (c) 2007 Elsevier B.V. All rights reserved.

关键词： Burrows-Wheeler transform suffix sorting suffix array space-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

space Saving by Dynamic Algebraization Based on Tree-Depth

引用

THEORY OF COMPUTING SYSTEMS 2017年第2期61卷 283-304页

作者： Furer, Martin Yu, Huiwen Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Google Inc 1600 Amphitheatre Pkwy Mountain View CA USA Penn State Univ University Pk PA 16802 USA

Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithms based on tree decompositions in polynomial space. We show how to use a tree decomposition and extend the algebraic techniques of Lokshtanov and Nederlof (In: 42nd ACM Symposium on Theory of Computing, pp. 321-330, 2010) such that a typical dynamic programming algorithm runs in time O*(2h), where h is the treedepth (Nesetril et al., Eur. J. Comb. 27( 6): 1022-1041, 2006) of a graph. In general, we assume that a tree decomposition of depth h is given. We apply our algorithm to the problem of counting perfect matchings on grids and show that it outperforms other polynomial-space solutions. We also apply the algorithm to other set covering and partitioning problems.

关键词： Dynamic programming Tree-depth Tree decomposition space-efficient algorithms Exponential time algorithms Zeta transform

来源：评论

学校读者我要写书评

暂无评论

Lightweight Data Indexing and Compression in External Memory

引用

ALGORITHMICA 2012年第3期63卷 707-730页

作者： Ferragina, Paolo Gagie, Travis Manzini, Giovanni Univ Piemonte Orientale Dipartimento Informat Alessandria Italy Univ Pisa Dipartimento Informat Pisa Italy Aalto Univ Dept Comp Sci & Engn Helsinki Finland

In this paper we describe algorithms for computing the Burrows-Wheeler Transform (bwt) and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are lightweight in the sense that, for an input of size n, they use only n bits of working space on disk while all previous approaches use I similar to(nlog n) bits. This is achieved by building the bwt directly without passing through the construction of the Suffix Array/Tree data structure. Moreover, our algorithms access disk data only via sequential scans, thus they take full advantage of modern disk features that make sequential disk accesses much faster than random accesses. We also present a scan-based algorithm for inverting the bwt that uses I similar to(n) bits of working space, and a lightweight internal-memory algorithm for computing the bwt which is the fastest in the literature when the available working space is o(n) bits. Finally, we prove lower bounds on the complexity of computing and inverting the bwt via sequential scans in terms of the classic product: internal-memory space x number of passes over the disk data, showing that our algorithms are within an O(log n) factor of the optimal.

关键词： Burrows-Wheeler transform Compressed indexes Data compression space-efficient algorithms External memory scan-based algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：