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

in-place algorithms for computing a largest clique in geometric intersection graphs

DISCRETE APPLIED MATHEMATICS 2014年 178卷 58-70页

作者： De, Minati Nandy, Subhas C. Roy, Sasanka Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Indian Stat Inst Kolkata 700108 India Chennai Math Inst Madras 603103 Tamil Nadu India

In this paper, we study the problem of designing in-place algorithms for finding the maximum clique in the intersection graphs of axis-parallel rectangles and disks in R-2. First, we propose an O(n(2) log n) time in-place algorithm for finding the maximum clique of the intersection graph of a set of n axis-parallel rectangles of arbitrary sizes. For the intersection graph of fixed height rectangles, the time complexity can be slightly improved to O(n log n + nK), where K is the size of the maximum clique. For disk graphs, we consider two variations of the maximum clique problem, namely geometric clique and graphical clique. The time complexity of our algorithm for finding the largest geometric clique is O(m log n + n(2)) where m is the number of edges in the disk graph, and it works for disks of arbitrary radii. For graphical clique, our proposed algorithm works for unit disks (i.e., of same radii) and the worst case time complexity is O(n(2) + m(n + K-3));m is the number of edges in the unit disk intersection graph and K is the size of the largest clique in that graph. It uses O(n(3)) time in-place computation of maximum matching in a bipartite graph, where the vertices are given in an array, and the existence of an edge between a pair of vertices can be checked by an oracle on demand (from problem specification) in O(1) time. This problem is of independent interest. All these algorithms need O(1) work space in addition to the input array. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Geometric intersection graphs Clique in-place algorithms Bipartite matching

来源：评论

学校读者我要写书评

暂无评论

in-place algorithms for exact and approximate shortest unique substring problems

引用

THEORETICAL COMPUTER SCIENCE 2017年 690卷 12-25页

作者： Hon, Wing-Kai Thankachan, Sharma V. Xu, Bojian Natl Tsing Hua Univ Dept Comp Sci Hsinchu 300 Taiwan Univ Cent Florida Dept Comp Sci Orlando FL 32816 USA Eastern Washington Univ Dept Comp Sci Cheney WA 99004 USA

We revisit the exact shortest unique substring (SUS) finding problem, and propose its approximate version where mismatches are allowed, due to its applications in subfields such as computational biology, We design a generic in-place framework that fits to solve both the exact and approximate k-mismatch SUS finding, using the minimum 2n memory words, each of inverted right perpendicular log(2)(n)inverted left perpendicular bits, plus n bytes space, where n is the input string size. By using the in-place framework, we can find the exact and approximate k-mismatch SUS for every string position using a total of O(n) and O(n(2)) time, respectively, regardless of the value of k. Our framework does not involve any compressed or succinct data structures and thus is practical and easy to implement. Experimental study shows that the peak memory usage of our proposal is consistently 9n bytes for any string of size n, validating the claim that our solution is in-place. Further, our proposal uses much less memory and is much faster than the currently best work that has implementation for exact SUS finding. (C) 2017 Elsevier B.V. All rights reserved.

关键词： String pattern matching Shortest unique substring in-place algorithms

来源：评论

学校读者我要写书评

暂无评论

in-place algorithms for Computing (Layers of) Maxima

引用

ALGORITHMICA 2010年第1期57卷 1-21页

作者： Blunck, Henrik Vahrenhold, Jan Tech Univ Dortmund D-44221 Dortmund Germany Aarhus Univ Ctr Mass Data Algorithm Ctr Danish Natl Res Fdn Dept Comp Sci DK-8200 Aarhus Denmark

We describe space-efficient algorithms for solving problems related to finding maxima among points in two and three dimensions. Our algorithms run in optimal O(n log n) time and occupy only constant extra space in add... 详细信息

关键词： in-place algorithms Pareto-optimal points Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Optimal in-place algorithms for 3-d Convex Hulls and 2-d Segment Intersection

Optimal In-Place Algorithms for 3-d Convex Hulls and 2-d Seg...

引用

25th Annual Symposium on Computational Geometry

作者： Chan, Timothy M. Chen, Eric Y. Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

ISBN: (纸本)9781605585017

We describe the first optimal randomized in-place algorithm for the basic 3-d convex hull problem (and, in particular, for 2-d Voronoi diagrams). The algorithm runs in O(n log n) expected time using only O(1) extra space;this improves the previous O(n log(3) n) bound by Bronnimann, Chan, and Chen [SoCG'04]. The same approach leads to an optimal randomized in-place algorithm for the 2-d line segment intersection problem, with O(n log n + K) expected running time for output size K, improving the previous O(n log(2) n + K) bound by Vahrenhold [WADS'05]. As a bonus, we also point out a simplification of a known optimal cache-oblivious (non-in-place) algorithm by Kumar and Ramos (2002) for 3-d convex hulls, and observe its applicability to 2-d segment intersection, extending a recent result for red/blue segment intersection by Arge, Molhave, and Zeh [ESA'08]. Our results are all obtained by standard random sampling techniques, with some interesting twists.

关键词： in-place algorithms convex hulls Voronoi diagrams segment intersection cache-oblivious algorithms

来源：评论

学校读者我要写书评

暂无评论

Frameworks for designing in-place graph algorithms

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 123卷 1-19页

作者： Chakraborty, Sankardeep Mukherjee, Anish Raman, Venkatesh Satti, Srinivasa Rao Univ Tokyo Tokyo Japan Univ Warsaw Warsaw Poland HBNI Inst Math Sci Mumbai Maharashtra India Norwegian Univ Sci & Technol Trondheim Norway

Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. More recently, several graph algorithms have been studied under ROM model. In this paper, we study graph algorithms under two different relaxations of ROM model, referred to as the implicit and rotate models, and show that these simple relaxations allow us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM model. All our algorithms are simple but quite subtle, and we believe that these models are practical enough to spur interest for other graph problems in these models. (C) 2021 The Author(s). Published by Elsevier Inc.

关键词： Graph algorithms in-place algorithms Implicit model ROM model BFS DFS Topological sorting

来源：评论

学校读者我要写书评

暂无评论

Optimal in-place and cache-oblivious algorithms for 3-d convex hulls and 2-d segment intersection

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2010年第8期43卷 636-646页

作者： Chan, Timothy M. Chen, Eric Y. Univ Waterloo Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada

We describe the first optimal randomized in-place algorithm for the basic 3-d convex hull problem (and, in particular, for 2-d Voronoi diagrams). The algorithm runs in O(n log n) expected time using only O(1) extra space;this improves the previous O(n log(3) n) bound by Bronnimann, Chan, and Chen (2004) [10]. The same approach leads to an optimal randomized in-place algorithm for the 2-d line segment intersection problem, with O(n logn + K) expected running time for output size K, improving the previous O(n log(2) n + K) bound by Vahrenhold (2007) [42]. As a bonus, we also point out a simplification of a known optimal cache-oblivious (non-in-place) algorithm by Kumar and Ramos (2002) [33] for 3-d convex hulls, and observe its applicability to 2-d segment intersection, extending a recent result for red/blue segment intersection by Arge, MOlhave, and Zeh (2008) [3]. Our results are all obtained by standard random sampling techniques, with some interesting twists. (C) 2010 Elsevier B.V. All rights reserved.

关键词： in-place algorithms Convex hulls Voronoi diagrams Segment intersection Cache-oblivious algorithms

来源：评论

学校读者我要写书评

暂无评论

In-place sorting with fewer moves

引用

INFORMATION PROCESSING LETTERS 1999年第1期70卷 31-37页

作者： Katajainen, J Pasanen, TA Turku Ctr Comp Sci FIN-20520 Turku Finland Univ Copenhagen Dept Comp DK-2100 Copenhagen E Denmark

It is shown that an array of n elements can be sorted using O(1) extra space, O(n log n/log log n) element moves, and a log(2)n + O(n log log n) comparisons. This is the first in-place sorting algorithm requiring o(n log n) moves in the worst case while guaranteeing O(n log n) comparisons, but due to the constant factors involved the algorithm is predominantly of theoretical interest. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： in-place algorithms sorting merging mergesort multiway merge

来源：评论

学校读者我要写书评

暂无评论

Optimizing stable in-place merging

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期302卷 191-210页

作者： Chen, JC Donghua Univ Dept Commun Shanghai 200051 Peoples R China

In 2000, Geffert et al. (Theoret. Comput. Sci. 237 (2000) 159) presented an asymptotically efficient algorithm for stable merging in constant extra space. The algorithm requires at most m(1)(t + 1) + m(2)/2' + o(m(1)) comparisons (t = [log(2)(m(2)/m(1))]) and 5m(2) + 12m(1) + o(m(1)) moves, where m(1) and m(2) are the sizes of two ordered sublists to be merged, and in m(1) less than or equal to m(2). This paper optimizes the algorithm. The optimized algorithm is simpler than their algorithm, and makes at most m(1)(t + 1) + m(2)/2' + o(m(1) + m(2)) comparisons and 6m(2) + 7m(1) + o(m(1) + m(2)) Moves. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： in-place algorithms stable merging sorting

来源：评论

学校读者我要写书评

暂无评论

Multiway in-place merging

引用

THEORETICAL COMPUTER SCIENCE 2010年第16-18期411卷 1793-1808页

作者： Geffert, Viliam Gajdos, Jozef Safarik Univ Dept Comp Sci Kosice 04001 Slovakia

We present an algorithm for asymptotically efficient k-way merging. Given an array A containing k sorted subsequences A(1),..., A(k) of respective lengths n(1),..., n(k), where Sigma(k)(i=1) n(i) = n, our algorithm merges A(1),..., A(k) into a single sorted sequence in-place and in linear time, performing c(k).n + o(n) element comparisons and 3.n + o(n) element moves, where c(k) = left perpendicularlg kright perpendicular + 2.(1 - 2(left perpendicularlg kright perpendicular)/k), which is a constant satisfying lg k <= c(k) <= inverted right perpendicularlg kinverted left perpendicular and, moreover, bounded by c(k) <= lg k+ 0.0861. The algorithm does not merge stably, however, it does not require that the elements in A are all distinct. (C) 2010 Elsevier B.V. All rights reserved.

关键词： in-place algorithms Merging Sorting

来源：评论

学校读者我要写书评

暂无评论

Asymptotically efficient in-place merging

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期237卷 159-181页

作者： Geffert, V Katajainen, J Pasanen, T Univ Copenhagen Dept Comp DK-2100 Copenhagen E Denmark Safarik Univ Dept Comp Sci SK-04154 Kosice Slovakia Turku Ctr Comp Sci FIN-20520 Turku Finland

Two linear-time algorithms for in-place merging are presented. Both algorithms perform at most m(t + 1) + n/2(t) + o(m) comparisons, where m and n are the sizes of the input sequences, m less than or equal to n, and t = [log(2)(n/m)]. The first algorithm is for unstable merging and it carries out no more than 3(n + m) + o(m) element moves. The second algorithm is for stable merging and it accomplishes at most 5n + 12m + o(m) moves. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： in-place algorithms merging sorting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：