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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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

分类表

所选分类

>> <<

限定检索结果

文献类型

42 篇 会议
32 篇 期刊文献

馆藏范围

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

日期分布

学科分类号

69 篇 工学
- 67 篇 计算机科学与技术...
- 13 篇 电气工程
- 11 篇 软件工程
- 10 篇 信息与通信工程
- 4 篇 控制科学与工程
- 1 篇 网络空间安全
14 篇 理学
- 14 篇 数学
- 1 篇 统计学（可授理学、...
1 篇 管理学
- 1 篇 管理科学与工程(可...

主题

74 篇 distributed grap...
7 篇 lower bounds
6 篇 congest
6 篇 maximal matching
5 篇 combinatorial to...
5 篇 distributed comp...
4 篇 minimum spanning...
4 篇 local model
4 篇 maximal independ...
3 篇 approximation al...
3 篇 network decompos...
3 篇 vertex coloring
3 篇 congest model
2 篇 fractional match...
2 篇 distributed veri...
2 篇 parallel graph a...
2 篇 consensus
2 篇 crash failures
2 篇 message complexi...
2 篇 edge coloring

机构

13 篇 swiss fed inst t...
7 篇 univ freiburg fr...
5 篇 technion haifa
5 篇 technion dept co...
4 篇 cnrs
4 篇 univ paris
3 篇 univ nacl autono...
3 篇 univ bordeaux bo...
3 篇 cnrs irif
3 篇 aalto univ espoo
3 篇 natl univ singap...
2 篇 weizmann inst sc...
2 篇 univ vienna fac ...
2 篇 univ paris cite
2 篇 swiss fed inst t...
2 篇 univ freiburg de...
2 篇 mit cambridge ma...
2 篇 eth zurich
2 篇 carnegie mellon ...
2 篇 cnrs bordeaux

作者

12 篇 ghaffari mohsen
9 篇 paz ami
8 篇 kuhn fabian
8 篇 fraigniaud pierr...
8 篇 censor-hillel ke...
7 篇 maus yannic
7 篇 suomela jukka
6 篇 brandt sebastian
5 篇 chang yi-jun
5 篇 uitto jara
5 篇 hirvonen juho
4 篇 roy matthieu
4 篇 rajsbaum sergio
4 篇 travers corentin
4 篇 castaneda armand...
3 篇 robinson peter
3 篇 balliu alkida
3 篇 olivetti dennis
3 篇 feuilloley laure...
3 篇 pandurangan gopa...

语言

73 篇 英文
1 篇 其他

检索条件"主题词=Distributed Graph Algorithms"

共 74 条记录，以下是51-60 订阅

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

详细简洁

排序：

A distributed (2+ε)-Approximation for Vertex Cover in O(log Δ/ε log log Δ) Rounds 16

A Distributed (2+ε)-Approximation for Vertex Cover in O(log...

引用

35th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing (PODC)

作者： Bar-Yehuda, Reuven Censor-Hillel, Keren Schwartzman, Gregory Technion Dept Comp Sci Haifa Israel

ISBN: (纸本)9781450339643

We present a simple deterministic distributed (2 vertical bar c) approximation algorithm for minimum weight vertex cover, which Delta completes in O(log Delta/epsilon log log A) rounds, where A is the maximum degree in the graph, for any epsilon > 0 which is at most O(1). For a constant c, this implies a constant approximation in O(log Delta/ log log Delta) rounds, which contradicts the lower bound of [KMW10].

关键词： local ratio distributed graph algorithms approximation vertex cover

来源：评论

学校读者我要写书评

暂无评论

Synchronous t-Resilient Consensus in Arbitrary graphs 1

引用

21st International Symposium on Stabilization, Safety, and Security of distributed Systems (SSS)

作者： Castaneda, Armando Fraigniaud, Pierre Paz, Ami Rajsbaum, Sergio Roy, Matthieu Travers, Corentin Univ Nacl Autonoma Mexico Mexico City DF Mexico CNRS Paris France Univ Paris Paris France UNAM CONACYT CNRS Lab Solomon Lefschetz UMI LaSoL Cuernavaca Morelos Mexico Univ Toulouse LAAS CNRS CNRS Toulouse France CNRS Bordeaux France Univ Bordeaux Bordeaux France

ISBN: (数字)9783030349929

ISBN: (纸本)9783030349929;9783030349912

We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius that considers all ways in which t nodes may crash, and present an algorithm that solves consensus in radius rounds. Then we derive a lower bound showing that our algorithm is optimal for vertex-transitive graphs, among oblivious algorithms.

关键词： Crash failures Consensus Combinatorial topology distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed Lower Bounds for Ruling Sets 61

Distributed Lower Bounds for Ruling Sets

引用

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

作者： Balliu, Alkida Brandt, Sebastian Olivetti, Dennis Univ Freiburg Freiburg Germany Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781728196213

Given a graph G = (V, E), an (alpha, beta)-ruling set is a subset S subset of V such that the distance between any two vertices in S is at least alpha, and the distance between any vertex in V and the closest vertex in S is at most beta. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a (2, beta)-ruling set (and hence also any (alpha, beta)-ruling set with alpha > 2) in the LOCAL model of distributed computing, we show the following, where n denotes the number of vertices, Delta the maximum degree, and c is some universal constant independent of n and Delta. Any deterministic algorithm requires Omega(min{log Delta/beta log log Delta, log(Delta) n}) rounds, for all beta <= c . min{root log Delta/log log Delta, log(Delta) n}. By optimizing Delta, this implies a deterministic lower bound of Omega(root log n/beta log log n) for all beta <= c 3 root log n/log log n. Any randomized algorithm requires Omega(min{log Delta/beta log log Delta, log(Delta) n}) rounds, for all beta <= c . min{root log Delta/log log Delta, log(Delta) n}. By optimizing Delta, this implies a randomized lower bound of Omega(root log log n/beta log log log n) for all beta <= c 3 root log log n/log log log n. For beta > 1, this improves on the previously best lower bound of Omega(log* n) rounds that follows from the 30-year-old bounds of Linial [FOCS'87] and Naor [***.'91] (resp. Omega(1) rounds if beta is an element of omega(log* n)). For beta = 1, i.e., for the problem of computing a maximal independent set (which is nothing else than a (2, 1)-ruling set), our results improve on the previously best lower bound of Omega(log* n) on trees, as our bounds already hold on trees.

关键词： Ruling set maximal independent set distributed graph algorithms lower bounds

来源：评论

学校读者我要写书评

暂无评论

A Sharp Threshold Phenomenon for the distributed Complexity of the Lovasz Local Lemma 19

A Sharp Threshold Phenomenon for the Distributed Complexity ...

引用

38th ACM Symposium on Principles of distributed Computing (PODC)

作者： Brandt, Sebastian Maus, Yannic Uitto, Jara Swiss Fed Inst Technol Zurich Switzerland Technion Haifa Israel Univ Freiburg Freiburg Germany

ISBN: (纸本)9781450362177

The Lovasz Local Lemma (LLL) says that, given a set of bad events that depend on the values of some random variables and where each event happens with probability at most p and depends on at most d other events, there is an assignment of the variables that avoids all bad events if the LLL criterion ep(d + 1) < 1 is satisfied. Nowadays, in the area of distributed graph algorithms it has also become a powerful framework for developing-mostly randomizedalgorithms. A classic result by Moser and Tardos yields an O(log(2) n) algorithm for the distributed Lovasz Local Lemma [JACM'10] if ep(d + 1) < 1 is satisfied. Given a stronger criterion, i.e., demanding a smaller error probability, it is conceivable that we can find better algorithms. Indeed, for example Chung, Pettie and Su [PODC'14] gave anO(log(epd2) n) algorithm under the epd(2) < 1 criterion. Going further, Ghaffari, Harris and Kuhn introduced an 2(O)(root log log n) time algorithm given d(8)p = O(1) [FOCS'18]. On the negative side, Brandt et al. and Chang et al. showed that we cannot go below Omega(log logn) (randomized) [STOC'16] and Omega(logn) (deterministic) [FOCS'16], respectively, under the criterion p <= 2(-d). Furthermore, there is a lower bound of Omega(log* n) that holds for any criterion. In this paper, we study the dependency of the distributed complexity of the LLL problem on the chosen LLL criterion. We show that for the fundamental case of each random variable of the considered LLL instance being associated with an edge of the input graph, that is, each random variable influences at most two events, a sharp threshold phenomenon occurs at p <= 2(-d) : we provide a simple deterministic (!) algorithm that matches the Omega(log* n) lower bound in bounded degree graphs, if p < 2(-d), whereas for p = 2(-d), the Omega(log logn) randomized and the Omega(logn) deterministic lower bounds hold. In many applications variables affect more than two events;our main contribution is to extend our algorithm to the c

关键词： Lovasz Local Lemma distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Agent-Driven BFS Tree in Anonymous graphs with Applications 1

引用

12th International Conference on Networked Systems (NETYS)

作者： Chand, Prabhat Kumar Kumar, Manish Molla, Anisur Rahaman Indian Stat Inst Kolkata Baranagar India Indian Inst Technol Chennai India

ISBN: (数字)9783031673214

ISBN: (纸本)9783031673207;9783031673214

Breadth-First-Search (BFS) trees serve a pivotal role in designing efficient graph algorithms due to their efficacy in traversing and exploring graph structures with a systematic layer-by-layer approach. This paper introduces an agent-based novel approach for constructing a BFS tree on an arbitrary anonymous graph G with n nodes and m edges using k >= n autonomous mobile agents. In this paper, we provide algorithms for BFS tree construction for different starting configurations and demonstrate their applications. Our main result considers the dispersed starting configuration (i.e., each node is occupied by a single agent at the start) and takes O(D Delta) rounds to execute, where D is the diameter and Delta is the highest degree of G. The algorithm assumes the knowledge of a root node for the BFS tree. We further continue our investigation for BFS tree construction with two other classical configurations, namely, rooted configuration and arbitrary configuration (with and without the knowledge of root) of the agents with some other follow-up configurations for k > n. In addition, the paper demonstrates the application of the BFS tree construction methodology in tasks like - checking a graph for bipartiteness and gathering agents into a single node, a fundamental task in distributed robotics.

关键词： Breadth First Search Tree Mobile Agents distributed Network algorithms Time Complexity Memory Complexity Bipartite graph Gathering distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

distributed MST and Routing in Almost Mixing Time 17

Distributed MST and Routing in Almost Mixing Time

引用

36th ACM Symposium on Principles of distributed Computing (PODC)

作者： Ghaffari, Mohsen Kuhn, Fabian Su, Hsin-Hao Swiss Fed Inst Technol Zurich Switzerland Univ Freiburg Freiburg Germany MIT Cambridge MA 02139 USA

ISBN: (纸本)9781450349925

We present a randomized distributed algorithm that computes a minimum spanning tree in tau(mix)(G) . 2(O(root log n log log n))) rounds, in any n-node graph G with mixing time tau(mix)(G). This result provides a sub-polynomial complexity for a wide range of graphs of practical interest, and goes below the celebrated (Omega) over tilde (D + root n) lower bound of Das Sarma et al. [STOC' 11] which holds for some worst-case general graphs. The core novelty in this result is a distributed method for permutation routing. In this problem, one is given a number of source-destination pairs, and we should deliver one packet from each source to its destination, all in parallel, in the shortest span of time possible. Our algorithm allows us to route and deliver all these packets in tau(mix)(G) .2(O(root log n log log n)) rounds, assuming that each node v is the source or destination for at most d(G)(v) packets. The main technical ingredient in this routing result is a certain hierarchical embedding of good-expansion random graphs on the base graph, which we believe can be of interest well beyond this work.

关键词： distributed graph algorithms CONGEST Model Routing Minimum Spanning Tree

来源：评论

学校读者我要写书评

暂无评论

Deterministic distributed Edge-Coloring via Hypergraph Maximal Matching 58

Deterministic Distributed Edge-Coloring via Hypergraph Maxim...

引用

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

作者： Fischer, Manuela Ghaffari, Mohsen Kuhn, Fabian Swiss Fed Inst Technol Dept Comp Sci CH-8092 Zurich Switzerland Univ Freiburg Dept Comp Sci D-79110 Freiburg Germany

ISBN: (纸本)9781538634646

We present a deterministic distributed algorithm that computes a (2 Delta - 1)-edge-coloring, or even list-edgecoloring, in any n-node graph with maximum degree Delta, in O(log(8) Delta . log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e.g., Open Problem 4 in the distributed graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2(O(root log n)) by Panconesi and Srinivasan [STOC' 92] and (O) over tilde (root Delta) + O(log* n) by Fraigniaud, Heinrich, and Kosowski [FOCS' 16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2 Delta - 1)-edgecoloring to poly(log log n) rounds. The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r - where each hyperedge has at most r vertices - with n nodes and maximum degree Delta, this algorithm computes a maximal matching in O(r(5) log(6+log r) Delta . log n) rounds. This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkin's book, a ((log Delta/epsilon)(O(log 1/epsilon)) - round deterministic algorithm for (1 + epsilon)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting lambda-arboricity graphs with out-degree at most inverted right perpendicular (1 + epsilon)lambda inverted left perpendicular, for any constant epsilon > 0, hence partially answering Open Problem 10 of Barenboim and Elkin's book.

关键词： distributed graph algorithms local algorithms deterministic distributed algorithms edge-coloring hypergraph maximal matching rounding linear programs

来源：评论

学校读者我要写书评

暂无评论

Strong-Diameter Network Decomposition 21

Strong-Diameter Network Decomposition

引用

40th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing (PODC)

作者： Chang, Yi-Jun Ghaffari, Mohsen Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450385480

Network decomposition is a central concept in the study of distributed graph algorithms. We present the first polylogarithmic-round deterministic distributed algorithm with small messages that constructs a strong-diameter network decomposition with polylogarithmic parameters. Concretely, a (C, D) strong-diameter network decomposition is a partitioning of the nodes of the graph into disjoint clusters, colored with C colors, such that neighboring clusters have different colors and the subgraph induced by each cluster has a diameter at most D. In the weak-diameter variant, the requirement is relaxed by measuring the diameter of each cluster in the original graph, instead of the subgraph induced by the cluster. A recent breakthrough of Rozhon and Ghaffari [STOC 2020] presented the first poly(log n)-round deterministic algorithm for constructing a weak-diameter network decomposition where C and D are both in poly(log n). Their algorithm uses small O(log n)-bit messages. One can transform their algorithm to a strong-diameter network decomposition algorithm with similar parameters. However, that comes at the expense of requiring unbounded messages. The key remaining qualitative question in the study of network decompositions was whether one can achieve a similar result for strong-diameter network decompositions using small messages. We resolve this question by presenting a novel technique that can transform any black-box weak-diameter network decomposition algorithm to a strong-diameter one, using small messages and with only moderate loss in the parameters.

关键词： ball carving distributed graph algorithms network decomposition

来源：评论

学校读者我要写书评

暂无评论

distributed MIS via All-to-All Communication 17

Distributed MIS via All-to-All Communication

引用

36th ACM Symposium on Principles of distributed Computing (PODC)

作者： Ghaffari, Mohsen Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450349925

Computing a Maximal Independent Set (MIS) is a central problem in distributed graph algorithms. This paper presents an improved randomized distributed algorithm for computing an MIS in an all-to-all communication distributed model, known as the congested clique model, defined as follows: Given a graph G = (V, E), initially each node knows only its neighbors. Communication happens in synchronous rounds over a complete graph, and per round each node can send O(logn) bits to each other node. We present a randomized algorithm that computes an MIS in (O) over tilde (log Delta/root log + 1) <= (O) over tilde(root log Delta rounds of congested clique, with high probability. Here Delta denotes the maximum degree in the graph. This improves quadratically on the O(log Delta algorithm of [Ghaffari, SODA' 16]. The core technical novelty in this result is a certain local sparsification technique for MIS, which we believe to be of independent interest.

关键词： distributed graph algorithms Maximal Independent Set (MIS) Congested Clique

来源：评论

学校读者我要写书评

暂无评论

Network Decomposition and distributed Derandomization 27th

Network Decomposition and Distributed Derandomization

引用

27th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Ghaffari, Mohsen Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9783030549206;9783030549213

We overview a recent line of work [Rozho.n and Ghaffari at STOC 2020;Ghaffari, Harris, and Kuhn at FOCS 2018;and Ghaffari, Kuhn, and Maus at STOC 2017], which proved that any (locallycheckable) graph problem that admits an efficient randomized distributed algorithm also admits an efficient deterministic distributed algorithm, thereby resolving several central and decades-old open problems in distributed graph algorithms. We present a short and self-contained version of the proofs, and conclude by discussing several related questions that remain open. This article accompanies a keynote talk of the author at the International Colloquium on Structural Information and Communication Complexity (SIROCCO) 2020. The writing is based on [24,28,45] and primarily targets non-experts.

关键词： distributed graph algorithms Derandomization Network decomposition LOCAL model

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

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

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：