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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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 条记录，以下是51-60 订阅

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

详细简洁

排序：

Fully dynamic all pairs shortest paths with real edge weights

Fully dynamic all pairs shortest paths with real edge weight...

引用

42nd Annual IEEE Symposium on Foundations of Computer Science

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

ISBN: (纸本)0769513905;0769513913

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

来源：评论

学校读者我要写书评

暂无评论

An Efficient Computational Framework for Studying dynamical Systems

An Efficient Computational Framework for Studying Dynamical ...

引用

15th International Symposium on Symbolic and Numeric algorithms for Scientific Computing (SYNASC)

作者： ElShaarawy, Islam Gomaa, Walid E JUST Alexandria Egypt

ISBN: (纸本)9781479930357

In this paper, we introduce a computational framework for studying dynamical systems. This framework can be used to prove the existence of certain behaviour in a given dynamical system at any finite (limited) resolution automatically. The proposed framework is based on approximating the phase space topology of a given dynamical system at a finite resolution by adaptively partitioning it at rational points. Dyadic rationals and partition elements with disjoint interiors are employed to build a transparent partition that enables constructing an ideal combinatorial representation of a given dynamical system. Moreover, we introduce a new algorithmic strategy that overcomes the dependence on initial conditions, supports deriving ubiquitous conclusions, enables finding bifurcation points up to certain precision, and (most importantly) is computationally efficient. A set of simple yet powerful dynamic graph algorithms that were developed to support the new strategy are described in details. As an application, invariant sets and bifurcation points of the logistic map were computed.

关键词： Finite Resolution Adaptive Partition Computer-Assisted Proofs Rigorous Numerics dynamical Systems Rigorous Simulation Bifurcation Analysis dynamic graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Experimental analysis of algorithms for updating minimum spanning trees on graphs subject to changes on edge weights

Experimental analysis of algorithms for updating minimum spa...

引用

6th International Workshop on Experimental algorithms

作者： Ribeiro, Celso C. Toso, Rodrigo F. Univ Fed Fluminense Inst Comp Rua Passo Patria 156 BR-24210240 Niteroi RJ Brazil

ISBN: (纸本)9783540728443

We consider the problem of maintaining a minimum spanning tree of a dynamically changing graph, subject to changes on edge weights. We propose an on-line fully-dynamic algorithm that runs in time O(vertical bar E vertical bar) when the easy-to-implement DRD-trees data structure for dynamic trees is used. Numerical experiments illustrate the efficiency of the approach.

关键词： minimum spanning trees dynamic graph algorithms experimental analysis algorithms data structures DRD-trees

来源：评论

学校读者我要写书评

暂无评论

dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

Dynamic Approximate All-Pairs Shortest Paths: Breaking the <...

引用

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

作者： Henzinger, Monika Krinninger, Sebastian Nanongkai, Danupon Univ Vienna Fac Comp Sci Vienna Austria Nanyang Technol Univ Div Math Sci Singapore Singapore

ISBN: (纸本)9780769551357

We study dynamic (1 + epsilon)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of (O) over tilde (mn) and constant query time by Roditty and Zwick [34] (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach [23];it has a total update time of O(mn(2)) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of (o) over tilde (n(5/2)) and constant query time that has an additive error of two in addition to the 1 broken vertical bar epsilon multiplicative error. This beats the previous (o) over tilde (mn) time when m = Omega(n(3/2)). Note that the additive error is unavoidable since, even in the static case, an O(n(3-delta))-time (a so-called truly subcubic) combinatorial algorithm with 1+epsilon multiplicative error cannot have an additive error less than 2-epsilon, unless we make a major breakthrough for Boolean matrix multiplication [19] and many other long-standing problems [40]. The algorithm can also be turned into a (2 + epsilon)approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + epsilon)approximation algorithm with (O) over tilde (n(5/2+O(1/root log n))) running time of Bernstein and Roditty [12] (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of (O) over tilde (mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + epsilon and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper [11]. In order to achieve our results, we introduce two new techniques: (1) A monotone Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree

关键词： dynamic graph algorithms all-pairs shortest paths derandomization emulator

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for Decremental Single-Source Reachability on Directed graphs 42nd

Improved Algorithms for Decremental Single-Source Reachabili...

引用

42nd International Colloquium on Automata, Languages and Programming (ICALP)

作者： Henzinger, Monika Krinninger, Sebastian Nanongkai, Danupon Univ Vienna Fac Comp Sci Vienna Austria KTH Royal Inst Technol Stockholm Sweden

ISBN: (纸本)9783662476727;9783662476710

Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with o(mn) total update time, wheremis the number of edges and n is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different m vs. n trade-off. For the case of m = Theta(n(1.5)) the running time is O(n(2.47)), just barely below mn = Theta(n(2.5)). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of (O) over tilde (min(m(7/6)n(2/3), m(3/4)n(5/4+o(1)), m(2/3)n(4/3+o(1))+ m(3/7)n(12/7+o)(1))). This gives, e.g., O(n(2.36)) for the notorious case m = Theta(n(1.5)). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.

关键词： dynamic graph algorithms Reachability

来源：评论

学校读者我要写书评

暂无评论

Fast dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers 61

Fast Dynamic Cuts, Distances and Effective Resistances via V...

引用

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Chen, Li Goranci, Gramoz Henzinger, Monika Peng, Richard Saranurak, Thatchaphol Georgia Tech Atlanta GA 30332 USA Univ Toronto Toronto ON Canada Univ Vienna Vienna Austria Toyota Technol Inst Nagoya Aichi Japan

ISBN: (纸本)9781728196213

We present a general framework of designing efficient dynamic approximate algorithms for optimization problems on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1) A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in (O) over tilde (n(2/3))(1) amortized time against an oblivious adversary, and (O) over tilde (m(3/4)) time against an adaptive adversary. (2) An incremental data structure that maintains O(1)-approximate shortest path in n(o(1)) time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in (O) over tilde (n(2/3+o(1))) amortized time per operation. (3) A fully-dynamic algorithm that approximates all-pair effective resistance up to an (1+epsilon) factor in (O) over tilde (n(2/3+o(1))epsilon(-O(1))) amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as j-trees) and approximately captures the cut-flow and metric structure of the graph. The O(1)-approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM '05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC '19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy.

关键词： dynamic graph algorithms maximum flow minimum cut shortest paths effective resistances approximate

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic Maximal Independent Set with Sublinear Update Time 2018

Fully Dynamic Maximal Independent Set with Sublinear Update ...

引用

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

作者： Assadi, Sepehr Onak, Krzysztof Schieber, Baruch Solomon, Shay Univ Penn Philadelphia PA 19104 USA IBM Res Yorktown Hts NY USA

ISBN: (纸本)9781450355599

A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch in 0(m) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time O(min{Delta, m(3/4)}), where A is a fixed bound on the maximum degree in the graph and m is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with O(min{A Delta, m(3/4)}) amortized message complexity, and O(1) amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC'16) that required an assumption of a non-adaptive oblivious adversary.

关键词： dynamic graph algorithms dynamic distributed algorithms maximal independent set

来源：评论

学校读者我要写书评

暂无评论

Deterministic Dispersion of Mobile Robots in dynamic Rings 18

Deterministic Dispersion of Mobile Robots in Dynamic Rings

引用

19th International Conference on Distributed Computing and Networking (ICDCN)

作者： Agarwalla, Ankush Augustine, John Moses, William K., Jr. Sankar, Madhav K. Sridhar, Arvind Krishna Natl Inst Technol Rourkela Dept Comp Sci & Engn Rourkela Odisha India Indian Inst Technol Madras Dept Comp Sci & Engn Chennai Tamil Nadu India Natl Inst Technol Tiruchirappalli Dept Comp Sci & Engn Tiruchirappalli Tamil Nadu India

ISBN: (纸本)9781450363723

In this work, we study the problem of dispersion of mobile robots on dynamic rings. The problem of dispersion of n robots on an n node graph, introduced by Augustine and Moses Jr. [2], requires robots to coordinate with each other and reach a configuration where exactly one robot is present on each node. This problem has real world applications and applies whenever we want to minimize the total cost of n agents sharing n resources, located at various places, subject to the constraint that cost of an agent moving to a different resource is comparatively much smaller than cost of multiple agents sharing a resource (e.g. smart electric cars sharing recharge stations). Study of this problem also provides indirect benefits to the studies of scattering on graphs, exploration by mobile robots, and load balancing on graphs. We solve the problem of dispersion in presence of two types of dynamism in the underlying graph: (i) vertex permutation and (ii) 1-interval connectivity. We introduce the notion of vertex permutation dynamism and have it mean that for a given set of nodes, in every round, the adversary ensures a ring structure is maintained, but the connections between the nodes may change. We use the idea of 1-interval connectivity from Di Luna et al. [11], where for a given ring, in each round, the adversary chooses at most one edge to remove. We assume robots have full visibility and present asymptotically time optimal algorithms to achieve dispersion in the presence of both types of dynamism when robots have chirality. When robots do not have chirality, we present asymptotically time optimal algorithms to achieve dispersion subject to certain constraints. Finally, we provide impossibility results for dispersion when robots have no visibility.

关键词： Dispersion Load balancing Mobile robots Collective robot exploration Scattering dynamic graph algorithms dynamic networks Deterministic algorithms Distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic Four-Vertex Subgraph Counting 1

Fully Dynamic Four-Vertex Subgraph Counting

引用

1st Symposium on Algorithmic Foundations of dynamic Networks, SAND 2022

作者： Hanauer, Kathrin Henzinger, Monika Hua, Qi Cheng

ISBN: (纸本)9783959772242

This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain the number of paths 1 of length three in deterministic amortized O(m2) update time, and any other connected four-vertex subgraph which is not a clique in deterministic amortized update time O(m3). Queries can be 2 answered in constant time. We also study the query times for subgraphs containing an arbitrary edge that is supplied only with the query as well as the case where only subgraphs containing a vertex s that is fixed beforehand are considered. For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far from (conditional) lower bounds: Based on the OMv conjecture we show that any dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or that counts length-3 paths takes update time Ω(m1/2−δ). Additionally, for 4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m1−δ) for any small constant δ > 0 for the amortized update time, assuming the static combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by Eppstein et al. [9] for these subgraphs cannot be improved by a polynomial factor. © Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua;licensed under Creative Commons License CC-BY 4.0

关键词： dynamic graph algorithms Motif Search Subgraph Counting

来源：评论

学校读者我要写书评

暂无评论

Constant-time dynamic (∆ + 1)-coloring 37

Constant-time dynamic (∆ + 1)-coloring

引用

37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020

作者： Henzinger, Monika Peng, Pan University of Vienna Faculty of Computer Science Vienna Austria Department of Computer Science University of Sheffield Sheffield United Kingdom

ISBN: (纸本)9783959771405

We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (∆ + 1)-vertex coloring of a graph with maximum degree at most ∆. This improves upon the previous O(log ∆)-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time, but is also optimal in the sense that already deciding whether a ∆-coloring exists in a dynamically changing graph with maximum degree at most ∆ takes Ω(log n) time per operation. © Monika Henzinger and Pan Peng;licensed under Creative Commons License CC-BY

关键词： dynamic graph algorithms graph coloring Random sampling

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

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

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：