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

dynamic 2-connectivity with backtracking

SIAM JOURNAL ON COMPUTING 1998年第1期28卷 10-26页

作者： La Poutre, JA Westbrook, J Univ Utrecht Dept Comp Sci NL-3508 TB Utrecht Netherlands AT&T Bell Labs Res Florham Pk NJ 07932 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA Princeton Univ Dept Comp Sci Princeton NJ 08540 USA

We give algorithms and data structures that maintain the 2-edge and 2-vertex-connected components of a graph under insertions and deletions of edges and vertices, where deletions occur in a backtracking fashion (i.e., deletions undo the insertions in the reverse order). Our algorithms run in Theta(log n) worst-case time per operation and use Theta(n) space, where n is the number of vertices. Using our data structure we can answer queries, which ask whether vertices u and v belong to the same 2-connected component, in Theta(log n) worst-case time.

关键词： dynamic graph algorithms backtracking

来源：评论

学校读者我要写书评

暂无评论

Single-source shortest paths and strong connectivity in dynamic planar graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 124卷 97-111页

作者： Charalampopoulos, Panagiotis Karczmarz, Adam Univ Warsaw Inst Informat Warsaw Poland Kings Coll London Dept Informat London England Efi Arazi Sch Comp Sci Interdisciplinary Ctr Herzliya Herzliyya Israel

We give a fully dynamic single-source shortest paths data structure for planar weighted digraphs with (O) over tilde (n(4/5)) worst-case update time and O(log(2) n) query time. Here, a single update can either change the graph by inserting or deleting an edge, or reset the source s of interest. All known non-trivial planarity-exploiting exact dynamic single-source shortest paths algorithms to date had polynomial query time. We then extend our approach, obtaining a data structure that can maintain a planar digraph under edge insertions and deletions, and is capable of returning the identifier of the strongly connected component of any query vertex. The worst-case update and query time bounds are the same as for our single-source distance oracle. To the best of our knowledge, this is the first fully dynamic strong-connectivity algorithm achieving both sublinear update time and polylogarithmic query time for an important class of digraphs. (C) 2021 Elsevier Inc. All rights reserved.

关键词： dynamic graph algorithms Planar graphs Single-source shortest paths Strong connectivity

来源：评论

学校读者我要写书评

暂无评论

Trade-Offs in dynamic Coloring for Bipartite and General graphs

引用

ALGORITHMICA 2023年第4期85卷 854-878页

作者： Kashyop, Manas Jyoti Narayanaswamy, N. S. Nasre, Meghana Potluri, Sai Mohith Indian Inst Technol Madras Dept Comp Sci & Engn Chennai Tamil Nadu India

The dynamic coloring problem has gained attention in the recent past. The focus has largely been on obtaining efficient update time algorithms using Delta + 1 or more colors and the trade-offs between update time and query time. Another important parameter in dynamic coloring is the number of recolorings per update which is addressed by the works of Barba et al. in WADS'17, and Solomon and Wein in ESA'18. In SODA'18, Bhattacharya et al. presented a randomized algorithm that uses Delta + 1 colors and achieves amortized O (log Omega) update time. In STACS'20, Henzinger and Peng presented a randomized (Delta + 1)-coloring algorithm with amortized O(1) update time. Independently on arXiv, Bhattacharya et al. also presented a randomized (Delta + 1)-coloring algorithm with amortized O(1) update time. While works of Bhattacharya et al., and Henzinger and Peng are very efficient in terms of update time, they do not address the number of recolorings per update. We bridge this gap by providing efficient update time algorithms with constant number of recolorings. Moreover our algorithm is deterministic as opposed to the works of Bhattacharya et al. in SODA'18, and Henzinger and Peng in STACS'20. Next, we study bipartite graphs which can be optimally colored in the static setting. We show that even in the incremental setting (where edges are added to the graph and no edge can be deleted), there is a bad update sequence which forces the update time to be at least Omega(logn) in the amortized setting and Omega(n) in the worst case. This possibly explains the lack of any results on dynamic coloring specific to bipartite graphs. We circumvent this lower bound by proposing two approaches. Firstly, we allow the use of more than two colors and obtain significantly better update time. Second, we introduce the idea of implicit coloring. If the color of a vertex is explicitly stored in a data structure and updated at end of every update then we call such an algorithm as explicit coloring

关键词： dynamic graph algorithms graph coloring

来源：评论

学校读者我要写书评

暂无评论

Average-case analysis of incremental topological ordering

引用

DISCRETE APPLIED MATHEMATICS 2010年第4期158卷 240-250页

作者： Ajwani, Deepak Friedrich, Tobias Int Comp Sci Inst Berkeley CA 94704 USA Ctr Mass Data Algorithm Aarhus Denmark

Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of incremental topological ordering algorithms. We prove an expected runtime of O(n(2) polylog(n)) under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (1990) [4], Katriel and Bodlaender (2006) 118], and Pearce and Kelly (2006) [23]. (C) 2009 Elsevier B.V. All rights reserved.

关键词： dynamic graph algorithms Average-case analysis Random graphs

来源：评论

学校读者我要写书评

暂无评论

A uniform approach to semi-dynamic problems on digraphs

引用

THEORETICAL COMPUTER SCIENCE 1998年第1期203卷 69-90页

作者： Cicerone, S Frigioni, D Nanni, U Pugliese, F Univ Rome La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Univ Aquila Dipartimento Matemat Pura & Applicata I-67010 Coppito LAquila Italy Univ Aquila Dipartimento Ingn Elettr I-67040 Laquila Italy

In this paper we propose a uniform approach to deal with incremental problems on digraphs and with decremental problems on dags generalizing a technique used by La Poutre and van Leeuwen in [17] for updating the transitive closure and the transitive reduction of a dag. We define a propagation property on a binary relationship over the vertices of a digraph as a simple sufficient condition to apply this approach. The proposed technique is suitable for a very simple implementation which does not depend on the particular problem;in other words, the same procedures can be used to deal with different problems by simply setting appropriate boundary conditions. In particular, we provide semi-dynamic algorithms and data structures for maintaining a binary relationship over the vertices of a digraph (dag) with n vertices and m edges, requiring O(nmax{q,m}) total time for any sequence of q edge insertions (deletions). This gives O(n) amortized time per operation over a sequence of Omega(m) edge insertions (deletions), Queries can be answered in constant time. The space required is O(n(2)). We apply the proposed technique to various problems about dominance, providing a solution to the problems of maintaining the dominance relationship, the dominator tree, and the nearest common dominator of a digraph in the incremental case, and of a dag in the decremental case;no dynamic solution was previously known for some of these problems. Finally we mention that the algorithms indeed work correctly also for interleaved sequences of insertion and deletion of edges in a dag, although the complexity bound holds for monotone sequence of updates only. (C) 1998-Elsevier Science B.V. All rights reserved.

关键词： dynamic graph algorithms transitive closure dominator tree directed acyclic graphs

来源：评论

学校读者我要写书评

暂无评论

Shortest Augmenting Paths for Online Matchings on Trees

引用

THEORY OF COMPUTING SYSTEMS 2018年第2期62卷 337-348页

作者： Bosek, Bartlomiej Leniowski, Dariusz Sankowski, Piotr Zych-Pawlewicz, Anna Jagiellonian Univ Theoret Comp Sci Dept Fac Math & Comp Sci Krakow Poland Univ Warsaw Inst Comp Sci Warsaw Poland

The shortest augmenting path (Sap) algorithm is one of the most classical approaches to the maximum matching and maximum flow problems, e.g., using it Edmonds and Karp (J. ACM 19(2), 248-264 1972) have shown the first strongly polynomial time algorithm for the maximum flow problem. Quite astonishingly, although it has been studied for many years already, this approach is far from being fully understood. This is exemplified by the online bipartite matching problem. In this problem a bipartite graph G = (W aSZ B, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. After arrival of this vertex we augment the current matching by using shortest augmenting path. It was conjectured by Chaudhuri et al. (INFOCOM'09) that the total length of all augmenting paths found by Sap is . However, no better bound than is known even for trees. In this paper we prove an upper bound for the total length of augmenting paths for trees.

关键词： Online matchings Bipartite matchings Approximate matchings Shortest augmenting paths dynamic graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic planarity testing with applications

引用

JOURNAL OF THE ACM 1999年第1期46卷 28-91页

作者： Galil, Z Italiano, GF Sarnak, N Columbia Univ Dept Comp Sci New York NY 10027 USA Univ Venice Dipartimento Matemat Applicata & Informat I-30123 Venice Italy IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

This paper introduces compressed certificates for planarity, biconnectivity and triconnectivity in planar graphs, and prove many structural properties of certificates in planar graphs. As an application of our compressed certificates, we develop efficient dynamic planar algorithms. In particular, we consider the following three operations on a planar graph G: (i) insert an edge if the resultant graph remains planar;(ii) delete an edge;and (iii) test whether an edge could be added to the graph without violating planarity. We show how to support each of the above operations in O(n(2/3)) time, where n is the number of vertices in the graph. The bound for tests and deletions is worst-case, while the bound for insertions is amortized. This is the first algorithm for this problem with sub-linear running time, and it affirmatively answers a question posed in Eppstein ct al. [1992]. We use our compressed certificates for biconnectivity and triconnectivity to maintain the biconnected and triconnected components of a dynamic planar graph. The time bounds are the same: O(n(2/3)) worst-case time per edge deletion, O(n(2/3)) amortized time per edge insertion, and O(n(2/3)) worst-case time to check whether two vertices are either biconnected or triconnected.

关键词： dynamic graph algorithms planar graphs planarity testing

来源：评论

学校读者我要写书评

暂无评论

Improved dynamic graph Coloring

引用

ACM TRANSACTIONS ON algorithms 2020年第3期16卷 41-41页

作者： Solomon, Shay Wein, Nicole Tel Aviv Univ POB 39040 IL-6997801 Tel Aviv Israel MIT 77 Massachusetts Ave Cambridge MA 02139 USA 77 Massachusetts Ave Cambridge MA 02139 USA

This article studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within n(1-is an element of) for any is an element of > 0, is NP-hard in static graphs, there is no hope to achieve any meaningful computational results for general graphs in the dynamic setting. It is therefore only natural to consider the combinatorial aspects of dynamic coloring or alternatively, study restricted families of graphs. Toward understanding the combinatorial aspects of this problem, one may assume a black-box access to a static algorithm for C-coloring any subgraph of the dynamic graph, and investigate the trade-off between the number of colors and the number of recolorings per update step. Optimizing the number of recolorings, sometimes referred to as the recourse bound, is important for various practical applications. In WADS '17, Barba et al. devised two complementary algorithms: for any beta > 0, the first (respectively, second) maintains an O(C beta n(1/beta)) (respectively, O(C beta))-coloring while recoloring O(beta) (respectively, O(beta n(1/beta))) vertices per update. Barba et al. also showed that the second trade-off appears to exhibit the right behavior, at least for beta = O(1): any algorithm that maintains a C-coloring of an n-vertex dynamic forest must recolor O(n(2/C(C-1))) vertices per update, for any constant C >= 2. Our contribution is twofold: We devise a new algorithm for general graphs that improves significantly upon the first trade-off in a wide range of parameters: for any beta > 0, we get a (O) over cap (C/beta log(2) n)-coloring with O(beta) recolorings per update, where the (O) over cap notation suppresses polyloglog(n) factors. In particular, for beta = O(1), we get constant recolorings with polylog(n) colors;not only is this an exponential improvement over the previous bound but also it unveils a rather surprising phenomenon: the trade-off between the numb

关键词： Coloring dynamic graph algorithms graph arboricity edge orientations

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic all pairs shortest paths with real edge weights

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2006年第5期72卷 813-837页

作者： Demetrescu, Camil Italiano, Giuseppe F. Univ Roma La Sapienza Dipartimento Informat & Sistemist Rome Italy Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod Rome Italy

We present the first fully dynamic algorithm for maintaining all pairs shortest paths in directed graphs with real-valued edge weights. Given a dynamic directed graph G such that each edge can assume at most S different real values, we show how to support updates in O(n(2.5)root/S log(3) n) amortized time and queries in optimal worst-case time. This algorithm is deterministic: no previous fully dynamic algorithm was known before for this problem. In the special case where edge weights can only be increased, we give a randomized algorithm with one-sided error that supports updates faster in O (S . n log(3) n) amortized time. We also show how to obtain query/update trade-offs for this problem, by introducing two new families of randomized algorithms. algorithms in the first family achieve an update bound of (O) over tilde (S . k . n(2))(1) and a query bound of (O) over tilde (n/k), and improve over the previous best known update bounds for k in the range (n/S)(1/3) <= k < (n/S)(1/2). algorithms in the second family achieve an update bound of <(O)over tilde>(S . k . n(2)) and a query bound of (O) over tilde (n(2)/k(2)), and are competitive with the previous best known update bounds (first family included) for k in the range (n/S)(1/6) <= k < (n/S)(1/3). (C) 2006 Elsevier Inc. All rights reserved.

关键词： dynamic graph algorithms shortest paths

来源：评论

学校读者我要写书评

暂无评论

dynamic subgraph connectivity with geometric applications

引用

SIAM JOURNAL ON COMPUTING 2006年第3期36卷 681-694页

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

Inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph G = ( V, E) and a subset of vertices S subset of V to support insertions/deletions in S and connectivity queries ( are two vertices connected?) in the subgraph induced by S. We develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using a combination of several simple ideas. Our method requires (O) over tilde(| E|(4 omega)/((3 omega+3))) = O(|E|(0.94)) amortized update time, and (O) over tilde(| E|(1/3)) query time, after (O) over tilde(| E|((5 omega+1)/(3 omega+3))) preprocessing time, where omega is the matrix multiplication exponent and (O) over tilde hides polylogarithmic factors.

关键词： data structures dynamic graph algorithms connectivity computational geometry

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：