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

THEORETICAL COMPUTER SCIENCE 2009年第41期410卷 4085-4093页

作者： Frandsen, Gudmund Skovbjerg Frandsen, Peter Frands Univ Aarhus Dept Comp Sci DK-8200 Aarhus N Denmark Ramboll Management AS DK-8200 Aarhus N Denmark

We consider maintaining information about the rank of a matrix under changes of the entries. For n x n matrices, we show an upper bound of O(n(1.575)) arithmetic operations and a lower bound of Omega(n) arithmetic operations per element change. The upper bound is valid when changing up to O(n(0.575)) entries in a single Column of the matrix. We also give an algorithm that maintains the rank using O(n(2)) arithmetic operations per rank one update. These bounds appear to be the first nontrivial bounds for the problem. The upper bounds are valid for arbitrary fields, whereas the lower bound is valid for algebraically closed fields. The upper bound for element updates uses fast rectangular matrix Multiplication, and the lower bound involves further development of an earlier technique for proving lower bounds for dynamic Computation of rational functions. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Matrix rank dynamic algorithms Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Deterministic dynamic Matching in O(1) Update Time

引用

ALGORITHMICA 2020年第4期82卷 1057-1080页

作者： Bhattacharya, Sayan Chakrabarty, Deeparnab Henzinger, Monika Univ Warwick Coventry England Dartmouth Coll Dept Comp Sci 6211 Sudikoff Lab Hanover NH 03755 USA Univ Vienna Vienna Austria

We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011), Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm's past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015);it had an approximation ratio of (2 + epsilon) and an amortized update time of O(log n/epsilon(2)). Our result can be generalized to give a fully dynamic O( f(3))-approximate algorithm with O( f(2)) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices.

关键词： dynamic algorithms Data structures Graph algorithms Matching Vertex cover

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic representations of interval graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 759卷 14-49页

作者： Crespelle, Christophe Univ Lyon UCB Lyon 1 ENS Lyon CNRSInriaLIP UMR 5668 15 Parvis Rene Descartes F-69342 Lyon France

We present a fully dynamic algorithm that maintains three different representations of an interval graph: a minimal interval model of the graph, the P Q-tree of its maximal cliques, and its modular decomposition. After each vertex or edge modification (insertion or deletion), the algorithm determines whether the new graph is an interval graph in O (n) time, and, in the positive, updates the three representations within the same complexity. Furthermore, we state that the modular decomposition tree of an interval graph and the P Q-tree of its maximal cliques are algorithmically equivalent and we completely explicit the relationship between the two structures. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Interval graphs dynamic algorithms PQ-tree Modular decomposition

来源：评论

学校读者我要写书评

暂无评论

Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 3056-3082页

作者： Agrawal, Sanjana Inkulu, R. Dept Comp Sci & Engn IIT Gauhati India

We devise an algorithm for maintaining the visibility polygon of any query point in a dynamic polygonal domain, i.e., as the polygonal domain is modified with vertex insertions and deletions to its obstacles, we update the data structures that store the visibility polygon of the query point. After preprocessing the initial input polygonal domain to build a few data structures, our algorithm takes O(k(lg vertical bar V P-P' (q) vertical bar) + (lg n')(2) + h) (resp. O(k (lg n')(2) + (lg vertical bar V P-P' (q) vertical bar) + h)) worst-case time to update data structures that store visibility polygon V P-P' (q) of a query point q when any vertex v is inserted to (resp. deleted from) any obstacle of the current polygonal domain P'. Here, n' is the number of vertices of P', h is the number of obstacles in P', V P-P', (q) is the visibility polygon of q in P' (vertical bar V P-P' (q) vertical bar is the number of vertices of V P-P' (q)), and k is the number of combinatorial changes in V P-P'(q) due to the insertion (resp. deletion) of v. As an application of the above algorithm, we also devise an algorithm for maintaining the visibility graph of a dynamic polygonal domain, i.e., as the polygonal domain is modified with vertex insertions and deletions to its obstacles, we update data structures that store the visibility graph of the polygonal domain. After preprocessing the initial input polygonal domain, our dynamic algorithm takes O(k(lg n')(2) + h) (resp. O(k (lg n')(2) + h) worst-case time to update data structures that store the visibility graph when any vertex v is inserted to (resp. deleted from) any obstacle of the current polygonal domain P'. Here, n' is the number of vertices of P', h is the number of obstacles in P', and k is the number of combinatorial changes in the visibility graph of P' due to the insertion (resp. deletion) of v.

关键词： Computational Geometry Visibility dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic APPROXIMATE ALL-PAIRS SHORTEST PATHS IN UNDIRECTED GRAPHS

引用

SIAM JOURNAL ON COMPUTING 2012年第3期41卷 670-683页

作者： Roditty, Liam Zwick, Uri Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

We obtain three new dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs: (i) For any fixed epsilon > 0, a decremental algorithm with an expected total running time of (O) over tilde (mn), where m is the number of edges and n is the number of vertices in the initial graph. Each distance query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 1 + epsilon. The algorithm uses (O) over tilde (n(2)) space. (ii) For any fixed integer k >= 1, a decremental algorithm with an expected total running time of (O) over tilde (mn). Each query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 2k - 1. This algorithm, however, uses only O(m + n(1+1/k)) space. It is obtained by dynamizing techniques of Thorup and Zwick. In addition to being more space efficient, this algorithm is also one of the building blocks used to obtain the first algorithm. (iii) For any fixed epsilon, delta > 0 and every t <= m(1/2-delta), a fully dynamic algorithm with an expected amortized update time of (O) over tilde (mn/t) and worst-case query time of O(t). The stretch of the returned distances is at most 1 + epsilon. All algorithms can also be made to work on undirected graphs with small integer edge weights. If the largest edge weight is b, then all bounds on the running times are multiplied by b.

关键词： dynamic algorithms transitive closure strongly connected components

来源：评论

学校读者我要写书评

暂无评论

A dynamic submatrix-based P300 online brain-computer interface

引用

BIOMEDICAL SIGNAL PROCESSING AND CONTROL 2015年第0期15卷 27-32页

作者： Shen, Jizhong Liang, Jianwei Shi, Jinhe Wang, Yupeng Zhejiang Univ Dept Informat Sci & Elect Engn Hangzhou 310027 Zhejiang Peoples R China

The P300 brain-computer interface (BCI) system relies on an oddball paradigm to elicit the P300. Besides the traditional row/column paradigm (RCP), many visual paradigms have been proposed for the P300 BCI. In our previous work, submatrix-based paradigm (sBP) was proposed and proven to be superior to the RCP in performance and user acceptability. To further improve the performance and realize an online BCI system, a dynamic SBP online BCI is proposed in this paper. The dynamic algorithm employs a threshold which dynamically limits the number of sequences. Based on analyzing the distribution characteristic of P300 in SBP, two threshold algorithms named the maximum value algorithm and the pseudo-kurtosis algorithm are proposed and compared. Online experimental results show that both dynamic algorithms can improve the performance of the SBP P300 speller, and the mean practical bit rate of the maximum value algorithm is 3436 bits/min, which is 9.04% higher than that of checkerboard paradigm (CBP) and 11.2% higher than that of Jin's n-flash adaptive system (NFA). (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Brain-computer interface Submatrix-based paradigm dynamic algorithms Online P300

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic shortest paths in digraphs with arbitrary arc weights

引用

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

作者： Frigioni, D Marchetti-Spaccamela, A Nanni, U Univ Aquila Dipartimento Ingn Elettr I-67040 Laquila Italy Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

We propose a new solution for the fully dynamic single source shortest paths problem in a directed graph G = (N, A) with arbitrary arc weights, that works for any digraph and has optimal space requirements and query time. If a negative-length cycle is introduced in the subgraph of G reachable from the source during an update operation, then it is detected by the algorithm. Zero-length cycles are explicitly handled. We evaluate the cost of the update operations as a function of a structural property of G and of the number of the output updates. We show that, if G has a k-bounded accounting function (as in the case of digraphs with genus, arboricity, degree, treewidth or page number bounded by k), then the update procedures require O(min{m, k(.)n(A)}(.)logn) worst case time for weight-decrease operations, and O(min{m(.)logn, k(.)(n(A) + n(B))(.)logn + n}) worst case time for weight-increase operations. Here, n = \N\, in \A\, n(A) is the number of nodes affected by the input update, that is the nodes changing either the distance or the parent in the shortest paths tree, and n(B) is the number of nonaffected nodes considered by the algorithm that also belong to zero-length cycles. If zero-length cycles are not allowed, then n(B) is zero and the bound for weight-increase operations is O(min{m(.)logn, k(.)n(A)(.)logn + n}). Similar amortized bounds hold if we perform also insertions and deletions of arcs. (C) 2003 Elsevier Inc. All rights reserved.

关键词： shortest paths dynamic algorithms output complexity zero-length cycles

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic algorithm for chordal graphs with O(1) query-time and O(n²) update-time

引用

THEORETICAL COMPUTER SCIENCE 2012年 445卷 82-92页

作者： Mezzini, Mauro Univ Roma La Sapienza Dept Comp Sci Rome Italy

We propose dynamic algorithms and data structures for chordal graphs supporting the following operation: determine if an edge can be added or removed from the graph while preserving the chordality in O(1) time. We show that the complexity of the algorithms for updating the data structures when an edge is actually inserted or deleted is O(n(2)) where n is the number of vertices of the graph. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Chordal graphs dynamic algorithms Minimal Triangulations

来源：评论

学校读者我要写书评

暂无评论

dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time

引用

JOURNAL OF THE ACM 2024年第5期71卷 1-32页

作者： Bhattacharya, Sayan Kiss, Peter Urak, Thatchaphol saran Wajc, David Univ Warwick Coventry England Univ Warwick Dept Comp Sci Coventry England Univ Michigan Ann Arbor MI USA Technion Israel Inst Technol Haifa Israel

We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2. Specifically, we obtain a 1+ root 21 + & varepsilon;approximate to 1.707+& varepsilon;approximation in bipartite graphs and a 1.973+& varepsilon;approximation in general graphs. We thus answer in the affirmative the value version of the major open question repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms' approximation and worst-case update time bounds both hold w.h.p. against adaptive adversaries. Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS'21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.

关键词： dynamic algorithms approximate matching

来源：评论

学校读者我要写书评

暂无评论

Fast dynamic Algorithm for Sequence Alignment Based on Bioinformatics algorithms

Fast Dynamic Algorithm for Sequence Alignment Based on Bioin...

引用

2011 IEEE International Conference on Intelligent Computing and Intelligent Systems(ICIS 2011)

作者： Sara Shehab Hany Mahgoub Arabi Keshk Waiel Fathi Computer Science Dept.Faculty of Computers&Info. Menoufia Univ.Shebin El-KomEgypt Operation Research Dept.Faculty of Computers&Info. Menoufia Univ.Shebin El-KomEgypt

This paper presents a new algorithm for DNA sequence alignment based on concepts from bioinformatics dynamic *** algorithm is called Fast dynamic Algorithm for Sequence Alignment (FDASA).The bioinformatics dynamic algorithms are used for computing the optimal alignment for the sequences,but the problem is these algorithms compute the unused data,this computation take more spaces in memory and decrease the *** new algorithm is proposed for overcoming the problems of dynamic algorithms;the memory spaces and *** experiments are applied on a collection of DNA sequences to compare the new algorithm’s results with the dynamic algorithms *** performance of proposed algorithm is compared with the previous dynamic algorithms for the execution time and memory *** results show that the new algorithm alignment between DNA sequences speed the performance and decrease the memory spaces used than that in the dynamic algorithms alignment for the same DNA ***,the execution time of proposed algorithm is much better than the previous dynamic algorithms.

关键词： FDAS Bioinformatics DNA Sequence alignment dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：