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

您好，读者！请登录

内蒙古大学图书馆

首页
概况
党建
资源
服务
科研支持
- 论文收录引用证明
- 科技查新
知识产权
档案馆
帮助

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入0个字，您还可以输入200个字

全部搜索
期刊论文
图书
学位论文
标准
纸本馆藏
外文资源发现
数据库导航
超星发现

高级检索

时间限定

出版年份：

文献类型

图书期刊文献学位论文多媒体

馆藏选择

电子馆藏纸本馆藏

核心期刊

全部期刊 SCI 收录期刊 SSCI 收录期刊 EI 收录期刊 CSCD 收录期刊 CSSCI 收录期刊

语言

中文英文

文献类型

期刊文献图书学位论文标准纸本馆藏

帮助

文字说明：

T=题名（书名、题名），A=作者（责任者），K=主题词，P=出版物名称，PU=出版社名称，O=机构（作者单位、学位授予单位、专利申请人），L=中图分类号，C=学科分类号，U=全部字段，Y=年（出版发行年、学位年度、标准发布年）

检索规则说明：

AND代表“并且”；OR代表“或者”；NOT代表“不包含”；(注意必须大写,运算符两边需空一格)

检索范例：

范例一：(K=图书馆学 OR K=情报学) AND A=范并思 AND Y=1982-2016
范例二：P=计算机应用与软件 AND (U=C++ OR U=Basic) NOT K=Visual AND Y=2011-2016

分类表

所选分类

>> <<

限定检索结果

文献类型

44 篇 期刊文献
30 篇 会议

馆藏范围

74 篇 电子文献
0 种 纸本馆藏

日期分布

学科分类号

69 篇 工学
- 67 篇 计算机科学与技术...
- 17 篇 软件工程
- 4 篇 电气工程
- 1 篇 控制科学与工程
31 篇 理学
- 31 篇 数学
1 篇 法学
- 1 篇 法学
1 篇 教育学
- 1 篇 教育学
1 篇 管理学
- 1 篇 管理科学与工程(可...

主题

74 篇 dynamic graph al...
8 篇 shortest paths
8 篇 data structures
6 篇 algorithms
4 篇 connectivity
4 篇 edge orientation...
4 篇 graph arboricity
4 篇 reachability
4 篇 graph coloring
3 篇 graph algorithms
3 篇 random graphs
3 篇 average-case ana...
3 篇 transitive closu...
2 篇 graph decomposit...
2 篇 graph connectivi...
2 篇 minimum spanning...
2 篇 buchi objectives
2 篇 graph games
2 篇 cell-probe lower...
2 篇 journey planning

机构

8 篇 univ vienna fac ...
5 篇 univ vienna aust...
4 篇 univ roma la sap...
4 篇 kth royal inst t...
3 篇 tel aviv univ po...
3 篇 georgia inst tec...
3 篇 indian inst tech...
3 篇 aarhus univ aarh...
3 篇 univ roma tor ve...
3 篇 univ roma tor ve...
2 篇 univ sci & techn...
2 篇 univ copenhagen ...
2 篇 univ roma la sap...
2 篇 inst math sci ch...
2 篇 max planck inst ...
2 篇 columbia univ de...
2 篇 google inc mount...
2 篇 univ waterloo sc...
2 篇 mit 77 massachus...
1 篇 ist austria klos...

作者

15 篇 henzinger monika
9 篇 nanongkai danupo...
7 篇 krinninger sebas...
5 篇 italiano giusepp...
4 篇 demetrescu camil
4 篇 italiano gf
4 篇 solomon shay
3 篇 bhattacharya say...
3 篇 narayanaswamy n....
3 篇 peng richard
3 篇 friedrich tobias
3 篇 saranurak thatch...
3 篇 kashyop manas jy...
3 篇 peng pan
2 篇 chan timothy m.
2 篇 henzinger mr
2 篇 brodal gerth sto...
2 篇 khan imran
2 篇 monika henzinger
2 篇 d'emidio mattia

语言

71 篇 英文
3 篇 其他

检索条件"主题词=dynamic graph algorithms"

共 74 条记录，以下是41-50 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

Decremental Single-Source Shortest Paths on Undirected graphs in Near-Linear Total Update Time 55

Decremental Single-Source Shortest Paths on Undirected Graph...

引用

55th Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Henzinger, Monika Krinninger, Sebastian Nanongkai, Danupon Univ Vienna Fac Comp Sci Vienna Austria

ISBN: (纸本)9781479965175

The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be easily solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach (JACM 1981) has been the fastest known algorithm for three decades. With the loss of a (1 + epsilon)-approximation factor, the running time was recently improved to O(n(2+o(1))) by Bernstein and Roditty (SODA 2011), and more recently to O(n(1.8+o(1)) + m(1+o(1))) by Henzinger, Krinninger, and Nanongkai (SODA 2014). In this paper, we finally bring the running time of this case down to near-linear: We give a (1+ epsilon)-approximation algorithm with O(m(1+o(1))) total update time, thus obtaining near-linear time. Moreover, we obtain O(m(1+o(1)) log W) time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn log W) time is the O(mn(0.986) log W)-time algorithm by Henzinger, Krinninger, and Nanongkai (STOC 2014) which works for the general weighted directed case. In contrast to the previous results which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (d, epsilon)-hop set introduced by Cohen (JACM 2000) in the PRAM literature. A (d, c)-hop set of a graph G = (V, E) is a set E' of weighted edges such that the distance between any pair of nodes in G can be (1+ epsilon)-approximated by their d-hop distance (given by a path containing at most d edges) on G' = (V, E boolean OR E'). Our algorithm can maintain an (n(o(1)), epsilon)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain the distances on this hop set, we develop a monotone bounded-hop Even-Shiloach t

关键词： dynamic graph algorithms single-source shortest paths

来源：评论

学校读者我要写书评

暂无评论

dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time 58

Dynamic Minimum Spanning Forest with Subpolynomial Worst-cas...

引用

58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Nanongkai, Danupon Saranurak, Thatchaphol Wulff-Nilsen, Christian KTH Royal Inst Technol Stockholm Sweden Univ Copenhagen Copenhagen Denmark

ISBN: (纸本)9781538634646

We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our algorithm guarantees an O(n(o(1))) worst-case update time with high probability. This significantly improves the two recent Las Vegas algorithms by Wulff-Nilsen [2] with update time O(n(0.5-epsilon)) for some constant epsilon > 0 and, independently, by Nanongkai and Saranurak [3] with update time O(n(0.494)) (the latter works only for maintaining a spanning forest). Our result is obtained by identifying the common framework that both two previous algorithms rely on, and then improve and combine the ideas from both works. There are two main algorithmic components of the framework that are newly improved and critical for obtaining our result. First, we improve the update time from O(n(0.5-epsilon)) in [2] to O(n(o(1))) for decrementally removing all low-conductance cuts in an expander undergoing edge deletions. Second, by revisiting the "contraction technique" by Henzinger and King [4] and Holm et al. [5], we show a new approach for maintaining a minimum spanning forest in connected graphs with very few (at most (1 + o(1))n) edges. This significantly improves the previous approach in [2], [3] which is based on Frederickson's 2-dimensional topology tree [6] and illustrates a new application to this old technique.

关键词： dynamic graph algorithms minimum spanning forests graph decomposition

来源：评论

学校读者我要写书评

暂无评论

New Deterministic Approximation algorithms for Fully dynamic Matching 16

New Deterministic Approximation Algorithms for Fully Dynamic...

引用

48th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Bhattacharya, Sayan Henzinger, Monika Nanongkai, Danupon IMSc Madras Tamil Nadu India Univ Vienna Vienna Austria KTH Stockholm Sweden

ISBN: (纸本)9781450341325

We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2 + epsilon)-approximate maximum matching in general graphs with O (poly(log n, 1/epsilon) update time. (2) An algorithm that maintains an al( approximation of the value of the maximum matching with 0(n(2)/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1 <= alpha(K) < 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(log n)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOGS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was 0(m(1/4)) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.

关键词： Data Structures dynamic graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications 2024

A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Spar...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Kyng, Rasmus Meierhans, Simon Gutenberg, Maximilian Probst Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9798400703836

We present a general toolbox, based on new vertex sparsifiers, for designing data structures to maintain shortest paths in graphs undergoing edge insertions and/or deletions. In particular, we obtain the following results: the first data structure to maintain m(o(1))-approximate all-pairs shortest paths (APSP) in an m-edge graph undergoing edge insertions and deletions with worst-case update time m(o(1)) and query time (O) over tilde (1), and a data structure to maintain a tree T that has diameter no larger than a subpolynomial factor than the underlying graph G that is undergoing edge insertions and deletions where each update is handled in amortized subpolynomial time, and a simpler and more efficient data structure to maintain a (1+epsilon)-approximate single-source shortest paths (SSSP) tree T in a graph undergoing edge deletions in amortized time m(o(1)) per update. All our data structures are deterministic. For the last two data structures, we further have that while the trees T are not subgraphs of G, they do embed with small edge congestion into G. This is in stark contrast to previous approaches and is particularly useful for algorithms that use these data structures internally to route flow along shortest paths. To illustrate the power of our new toolbox, we show that our SSSP data structure can be used directly to give a deterministic implementation of the classic MWU algorithm for approximate undirected minimum-cost flow running in time m(1+o(1)). Previously, Bernstein-Gutenberg-Saranurak [FOCS21] had built a randomized data structure achieving m(1+o(1)) time whp. By using our SSSP data structure in the recent almost-linear time algorithm for computing Gomory-Hu trees by Abboud-Li-Panigrahi-Saranurak [FOCS23], we simplify their algorithm significantly and slightly improve their runtime. To obtain our toolbox, we give the first algorithm that, given a graph G undergoing edge insertions and deletions and a dynamic terminal set A, maintains a vertex sparsif

关键词： Shortest-Paths dynamic graph algorithms All-Pair Shortest-Paths

来源：评论

学校读者我要写书评

暂无评论

Sublinear-Time Decremental algorithms for Single-Source Reachability and Shortest Paths on Directed graphs 14

Sublinear-Time Decremental Algorithms for Single-Source Reac...

引用

46th Annual ACM Symposium on Theory of Computing (STOC)

作者： Henzinger, Monika Krinninger, Sebastian Nanongkai, Danupon Univ Vienna Fac Comp Sci Vienna Austria Brown Univ ICERM Providence RI 02912 USA Nanyang Technol Univ Singapore 637371 Singapore

ISBN: (纸本)9781450327107

We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach (JACM 1981);it has O(1) query time and O(mn) total update time (i.e., linear amortized update time if all edges are deleted). This algorithm serves as a building block for several other dynamic algorithms. The question whether its total update time can be improved is a major, long standing, open problem. In this paper, we answer this question affirmatively. We obtain a randomized algorithm which, in a simplified form, achieves an O(mn(0.984)) expected total update time for SSR and (1 + epsilon)-approximate SSSP, where O(.) hides poly log n. We also extend our algorithm to achieve roughly the same running time for Strongly Connected Components (SCC), improving the algorithm of Roditty and Zwick (FOCS 2002), and an algorithm that improves the O(mn log W)-time al gorithm of Bernstein (STOC 2013) for approximating SSSP on weighted directed graphs, where the edge weights are integers from 1 to W. All our algorithms have constant query time in the worst case.

关键词： dynamic graph algorithms reachability shortest paths

来源：评论

学校读者我要写书评

暂无评论

Improved Worst -Case Deterministic Parallel dynamic Minimum Spanning Forest 18

Improved Worst -Case Deterministic Parallel Dynamic Minimum ...

引用

30th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Kopelowitz, Tsvi Porat, Ely Rosenmutter, Yair Bar Ilan Univ Ramat Gan Israel

ISBN: (纸本)9781450357999

This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with n vertices and m edges while supporting edge insertions and deletions. We show that one can solve the dynamic MSF problem using O(jt) processors and O(log n) worst-case update time, for a total of ONT. log n) work. This improves on the work of Ferragina [IPPS 1995] which costs O(log n) worst-case update time and 0(n213 log);171) work.

关键词： dynamic connectivity minimum spanning forest dynamic graph algorithms pram model

来源：评论

学校读者我要写书评

暂无评论

Updating directed minimum cost spanning trees

引用

5th International Workshop on Experimental algorithms (WEA 2006)

作者： Pollatos, Gerasimos G. Telelis, Orestis A. Zissimopoulos, Vassilis Univ Athens Dept Informat & Telecommun Hellas Greece

ISBN: (纸本)3540345973

We consider the problem of updating a directed minimum cost spanning tree (DMST), when edges are deleted from or inserted to a weighted directed graph. This problem apart from being a classic for directed graphs, is to the best of our knowledge a wide open aspect for the field of dynamic graph algorithms. Our contributions include results on the hardness of updates, a dynamic algorithm for updating a DMST, and detailed experimental analysis of the proposed algorithm exhibiting a speedup factor of at least 2 in comparison with the static practice.

关键词： branchings dynamic graph algorithms data structures

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic Spectral Vertex Sparsifiers and Applications 2019

Fully Dynamic Spectral Vertex Sparsifiers and Applications

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Durfee, David Gao, Yu Goranci, Gramoz Peng, Richard Georgia Inst Technol Atlanta GA 30332 USA Univ Vienna Fac Comp Sci Vienna Austria

ISBN: (纸本)9781450367059

We study dynamic algorithms for maintaining spectral vertex sparsifiers of graphs with respect to a set of terminals T of our choice. Such objects preserve pairwise resistances, solutions to systems of linear equations, and energy of electrical flows between the terminals in T. We give a data structure that supports insertions and deletions of edges, and terminal additions, all in sublinear time. We then show the applicability of our result to the following problems. (1) A data structure for dynamically maintaining solutions to Laplacian systems Lx = b, where L is the graph Laplacian matrix and b is a demand vector. For a bounded degree, unweighted graph, we support modifications to both L and b while providing access to epsilon-approximations to the energy of routing an electrical flow with demand b, as well as query access to entries of a vector x such that parallel to(x) over tilde - L dagger b parallel to(L) <= epsilon parallel to L dagger b parallel to(L) in (O) over tilde (n(11/12)epsilon(-5)) expected amortized update and query time. (2) A data structure for maintaining fully dynamic All-Pairs Effective Resistance. For an intermixed sequence of edge insertions, deletions, and resistance queries, our data structures returns (1 +/-epsilon)-approximation to all the resistance queries against an oblivious adversary with high probability. Its expected amortized update and query times are (O) over tilde (min(m(3/4), n(5/6)epsilon(-2))epsilon(-4)) on an unweighted graph, and (O) over tilde (n(5/6)epsilon(-6)) on weighted graphs. The key ingredients in these results are (1) the intepretation of Schur complement as a sum of random walks, and (2) a suitable choice of terminals based on the behavior of these random walks to make sure that the majority of walks are local, even when the graph itself is highly connected and (3) maintenance of these local walks and numerical solutions using data structures. These results together represent the first data structures for main

关键词： dynamic graph algorithms Schur complement effective resistance graph Laplacian

来源：评论

学校读者我要写书评

暂无评论

Unifying and Strengthening Hardness for dynamic Problems via the Online Matrix-Vector Multiplication Conjecture 15

Unifying and Strengthening Hardness for Dynamic Problems via...

引用

47th Annual ACM Symposium on Theory of Computing (STOC) held as part of the Federated Computing Research Conference

作者： Henzinger, Monika Krinninger, Sebastian Nanongkai, Danupon Saranurak, Thatchaphol Univ Vienna Vienna Austria KTH Royal Inst Technol Stockholm Sweden

ISBN: (纸本)9781450335362

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v(1), ... , v(n), one by one. After seeing each vector we have to output the product Mv(i) before we can see the next vector. A naive algorithm can solve this problem using O(n(3)) time in total, and its running time can be slightly improved to O(n(3)/log(2) n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic (P(n(3-epsilon))) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "Strassen-like algorithms" [Ballard et al. SPAA'11]. The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures - such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase thus providing a uniform way to prove polynomial hardness results for dynamic algorithms;some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully-dynamic densest subgraph and diameter problems.

关键词： dynamic graph algorithms lower bounds matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

Average Update Times for Fully-dynamic All-Pairs Shortest Paths

引用

19th Annual International Symposium on algorithms and Computation (ISAAC)

作者： Friedrich, Tobias Hebbinghaus, Nils Max Planck Inst Informat Saarbrucken Germany

ISBN: (纸本)9783540921813

We study the fully-dynamic all pairs shortest path problem for graphs with arbitrary non-negative edge weights. It is known for digraphs that an update of the distance matrix costs (O) over tilde (n(2.75))(1) worst-case time [Thorup, STOC '05) and (O) over tilde (n(2)) amortized time [Demetrescu and Italiano, JACM '04] where n is the number of vertices. We present the first average-case analysis of the undirected problem. For a random update we show that the expected time per update is bounded by O(n(4/3+epsilon)) for all epsilon > 0.

关键词： dynamic graph algorithms shortest paths average-case analysis random graphs

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

全选清除本页清除全部题录导出标记到“检索档案”

共8页 << < 1 2 3 4 5 6 7 8 > >>

检索报告对象比较合并检索0

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

电话和邮箱必须正确填写，我们会与您联系确认。

联系人：

所在院系：

联系邮箱：

联系电话：

内蒙古自治区呼和浩特市赛罕区大学西街235号邮编: 010021

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：