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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

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

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

详细简洁

排序：

A Topological Perspective on distributed Network algorithms 26th

A Topological Perspective on Distributed Network Algorithms

引用

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

作者： 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 CNRS Toulouse France CNRS Bordeaux France Univ Bordeaux Bordeaux France

ISBN: (纸本)9783030249212;9783030249229

More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the LOCAL model and dynamic networks.

关键词： distributed computing distributed graph algorithms Combinatorial topology

来源：评论

学校读者我要写书评

暂无评论

An Automatic Speedup Theorem for distributed Problems 19

An Automatic Speedup Theorem for Distributed Problems

引用

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

作者： Brandt, Sebastian Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450362177

Recently, Brandt et al. [STOC'16] proved a lower bound for the distributed Lovasz Local Lemma, which has been conjectured to be tight for sufficiently relaxed LLL criteria by Chang and Pettie [FOCS'17]. At the heart of their result lies a speedup technique that, for graphs of girth at least 2t + 2, transforms any t -round algorithm for one specific LLL problem into a (t - 1)-round algorithm for the same problem. We substantially improve on this technique by showing that such a speedup exists for any locally checkable problem Pi, with the difference that the problem Pi(1) the inferred (t - 1)-round algorithm solves is not (necessarily) the same problem as Pi. Our speedup is automatic in the sense that there is a fixed procedure that transforms a description for Pi into a description for Pi(1) and reversible in the sense that any (t - 1)-round algorithm for Pi(1) can be transformed into a t-round algorithm for Pi. In particular, for any locally checkable problem. with exact deterministic time complexity T (n, Delta) <= t on graphs with n nodes, maximum node degree Delta, and girth at least 2t + 2, there is a sequence of problems Pi(1), Pi(2),... with time complexities T (n, Delta) - 1, T (n, Delta) - 2,..., that can be inferred from Pi. As a first application of our generalized speedup, we solve a longstanding open problem of Naor and Stockmeyer [STOC'93]: we show that weak 2-coloring in odd-degree graphs cannot be solved in o(log*Delta) rounds, thereby providing a matching lower bound to their upper bound.

关键词： distributed graph algorithms locally checkable problems weak coloring

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for Maximal Matchings and Maximal Independent Sets 60

Lower Bounds for Maximal Matchings and Maximal Independent S...

引用

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

作者： Balliu, Alkida Brandt, Sebastian Hirvonen, Juho Olivetti, Dennis Rabie, Mikael Suomela, Jukka Aalto Univ Espoo Finland Swiss Fed Inst Technol Zurich Switzerland Sorbonne Univ LIP6 Paris France

ISBN: (纸本)9781728149523

There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Delta + log* n) communication rounds;here n is the number of nodes and Delta is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: these problems cannot be solved in o(log* n) rounds even if Delta = 2. However, the dependency on Delta is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds. We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in o(Delta + log log n/log log log n) rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in o(Delta + log n/log log n) rounds;this is an improvement over prior lower bounds also as a function of n.

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

来源：评论

学校读者我要写书评

暂无评论

distributed Half-Integral Matching and Beyond 30th

Distributed Half-Integral Matching and Beyond

引用

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

作者： Dahal, Sameep Suomela, Jukka Aalto Univ Espoo Finland

ISBN: (纸本)9783031327322;9783031327339

By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires Omega(log* n) communication rounds, while it is possible to find a maximal fractional matching in O(1) rounds in bounded-degree graphs. However, all prior O(1)-round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from {0, 1/2, 1}. We show that the use of finegrained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree Delta = 2d, and any distributed graph algorithm with round complexity T(Delta) that only depends on Delta and is independent of n, we show that the algorithm has to use fractional values with a denominator at least 2(d). We give a new algorithm that shows that this is also sufficient.

关键词： maximal matching fractional matching half-integral matching distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved Partitioning graph Embedding Framework for Small Cluster 14th

Improved Partitioning Graph Embedding Framework for Small Cl...

引用

14th International Conference on Knowledge Science, Engineering, and Management (KSEM)

作者： Sun, Ding Huang, Zhen Li, Dongsheng Ye, Xiangyu Wang, Yilin Natl Univ Def Technol Changsha 410073 Hunan Peoples R China Natl Key Lab Parallel & Distributed Proc Changsha Peoples R China

ISBN: (纸本)9783030821364;9783030821357

graph embedding is a crucial method to produce node features that can be used for various machine learning tasks. Because of the large number of embedded parameters in large graphs, a single machine cannot load the entire graph into GPUs at once, so a partitioning strategy is required. However, there are some problems with partitioning strategies. Firstly, partitioning introduces data I/O and processing overhead, which increases training time, especially on the cluster with a small number of sites. Secondly, partitioning can affect the performance of the model. For multi-relation graphs, this effect is often negative. To address these problems, we propose the training pipeline and random partitions recombination methods. The training pipeline can reduce the time overhead by masking data loading time to GPU computation, and partitions recombination can effectively improve multi-relation model performance. We conducted experiments on multi-relation graphs and social networks, and the results show that both methods are effective.

关键词： graph embedding Knowledge graphs Partitioning graph framework GPU distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved distributed Delta-Coloring 18

Improved Distributed Delta-Coloring

引用

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

作者： Ghaffari, Mohsen Hirvonen, Juho Kuhn, Fabian Maus, Yannic Swiss Fed Inst Technol Zurich Switzerland Univ Freiburg Freiburg Germany

ISBN: (纸本)9781450357951

We present a randomized distributed algorithm that computes a A coloring in any non-complete graph with maximum degree A > 4 in 0 (log A) + 20 (/log log n) rounds, as well as a randomized algorithm that computes a A-coloring in 0((log log n)2) rounds when A E [3, 0(1)]. Both these algorithms improve on an 0 (log3 n/log A) round algorithm of Panconesi and Srinivasan [STOC'1993], which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Q (log log n) round lower bound of Brandt et al. [STOC'16].

关键词： distributed computing distributed graph algorithms graph coloring

来源：评论

学校读者我要写书评

暂无评论

Preparing for Disaster: Leveraging Precomputation to Efficiently Repair graph Structures Upon Failures 22

Preparing for Disaster: Leveraging Precomputation to Efficie...

引用

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

作者： Newport, Calvin Vaidya, Nitin Weaver, Alex Georgetown Univ Washington DC 20057 USA

ISBN: (纸本)9781450391467

distributed algorithms for constructing structures such as a maximal independent set (MIS) or maximal matching (MM) are wellstudied in standard message-passing network models. In this paper, we consider a natural variant of this problem in which we begin with an instance of the graph structure and partition our algorithm execution that follows into two stages. During the first stage after the graph structure is calculated, some additional precomputation is done. In the second stage, an arbitrary collection of.. nodes are crashed. The goal is to then repair the structure as efficiently as possible. We are interested in the circumstances under which the repair can be faster than the time required to build the structure from scratch, and focus, in particular, on trade-offs in which extra precomputation rounds during the first stage can be traded for faster repairs during the second.

关键词： distributed graph algorithms Maximal Independent Set Maximal Matching Fault Tolerance

来源：评论

学校读者我要写书评

暂无评论

distributed Community Detection with the WCC Metric 24

Distributed Community Detection with the WCC Metric

引用

24th International Conference on World Wide Web (WWW)

作者： Saltz, Matthew Prat-Perez, Arnau Dominguez-Sal, David Univ Politecn Cataluna DAMA UPC E-08028 Barcelona Spain

ISBN: (纸本)9781450334730

Community detection has become an extremely active area of research in recent years, with researchers proposing various new metrics and algorithms to address the problem. Recently, the Weighted Community Clustering (WCC) metric was proposed as a novel way to judge the quality of a community partitioning based on the distribution of triangles in the graph, and was demonstrated to yield superior results over other commonly used metrics like modularity. The same authors later presented a parallel algorithm for optimizing WCC on large graphs. In this paper, we propose a new distributed, vertex-centric algorithm for community detection using the WCC metric. Results are presented that demonstrate the algorithm's performance and scalability on up to 32 worker machines and real graphs of up to 1.8 billion edges. The algorithm scales best with the largest graphs, finishing in just over an hour for the largest graph, and to our knowledge, it is the first distributed algorithm for optimizing the WCC metric.

关键词： Community detection distributed graph algorithms

来源：评论

学校读者我要写书评

暂无评论

On Local distributed Sampling and Counting 18

On Local Distributed Sampling and Counting

引用

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

作者： Feng, Weiming Yin, Yitong Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China

ISBN: (纸本)9781450357951

In classic distributed graph problems, each instance on a graph specifies a space of feasible solutions (e.g. all proper (Delta + 1)-list-colorings of the graph), and the task of distributed algorithm is to construct a feasible solution using local information. We study distributed sampling and counting problems, in which each instance specifies a joint distribution of feasible solutions. The task of distributed algorithm is to sample from this joint distribution, or to locally measure the volume of the probability space via the marginal probabilities. The latter task is also known as inference, which is a local counterpart of counting. For self-reducible classes of instances, the following equivalences are established in the LOCAL model up to polylogarithmic factors: For all joint distributions, approximate inference and approximate sampling are computationally equivalent. For all joint distributions defined by local constraints, exact sampling is reducible to either one of the above tasks. If further, sequentially constructing a feasible solution is trivial locally, then all above tasks are easy if and only if the joint distribution exhibits strong spatial mixing. Combining with the state of the arts of strong spatial mixing, we obtain efficient sampling algorithms in the LOCAL model for various important sampling problems, including: an O(root Delta log(3) n)-round algorithm for exact sampling matchings in graphs with maximum degree Delta, and an O(log(3) n)-round algorithm for sampling according to the hardcore model (weighted independent sets) in the uniqueness regime, which along with the Omega(diam) lower bound in [3] for sampling according to the hardcore model in the non-uniqueness regime, gives the first computational phase transition for distributed sampling.

关键词： distributed graph algorithms local computation sampling algorithms Gibbs distribution strong spatial mixing

来源：评论

学校读者我要写书评

暂无评论

Low-Congestion Shortcuts for graphs Excluding Dense Minors 21

Low-Congestion Shortcuts for Graphs Excluding Dense Minors

引用

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

作者： Ghaffari, Mohsen Haeupler, Bernhard Swiss Fed Inst Technol Zurich Switzerland Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450385480

We prove that any n-node graph G with diameter D admits shortcuts with congestion O(delta D log n) and dilation O(delta D), where delta is the maximum edge-density of any minor of G. Our proof is simple and constructive with a (Theta) over tilde(delta D)-round(1) distributed construction algorithm. Our results are tight up to logarithmic factors and generalize, simplify, unify, and strengthen several prior results. For example, for graphs excluding a fixed minor, i.e., graphs with constant delta, only (O) over tilde (D-2) bound was known based on a very technical proof that relies on the Robertson-Seymour graph Structure Theorem. A direct consequence of our result is this: many graph families, including any minor-excluded ones, have near-optimal (Theta) over tilde (D)-round distributed algorithms for many fundamental communication primitives and optimization problems in the standard synchronous message-passing model with logarithmic message sizes, i.e., the CONGEST model. These problems include minimum spanning tree, minimum cut approximation, and shortest-path approximations.

关键词： distributed graph algorithms low-congestion shortcuts minor-exluded graphs planar graphs congestion dilation minimum spanning tree

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

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

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：