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

20th International Conference on distributed Computing and Networking (ICDCN)

作者： Saikia, Parikshit Karmakar, Sushanta Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati 781039 India

ISBN: (纸本)9781450360944

The Steiner tree problem is a classical and fundamental problem in combinatorial optimization. The best known deterministic distributed algorithm for the Steiner tree problem in the CONGEST model was proposed by Lenzen and Patt-Shamir [25] that constructs a Steiner tree whose cost is optimal upto a factor of 2 and the round complexity is (O) over tilde (S + root min{St, n}) for a graph of n nodes and t terminals, where S is the shortest path diameter of the graph. Note here that the (O) over tilde(center dot) notation hides polylogarithmic factors in n. In this paper we present a simple deterministic distributed algorithm for constructing a Steiner tree in the CONGEST model with an approximation factor 2(1 - 1/l) of the optimal where l is the number of terminal leaf nodes in the optimal Steiner tree. The round complexity of our algorithm is O(S + root n log* n) and the message complexity is O(Delta(n - t)S + n(3/2)), where. is the maximum degree of a vertex in the graph. Our algorithm is based on the computation of a sub-graph called the shortest path forest for which we present a separate deterministic distributed algorithm with round and message complexities of O(S) and O(Delta(n - t)S) respectively.

关键词： Steiner tree shortest path forest distributed approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

distributed approximation algorithms for Steiner Tree in the CONGESTED CLIQUE

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2020年第7期31卷 941-968页

作者： Saikia, Parikshit Karmakar, Sushanta Indian Inst Technol Dept Comp Sci & Engn Gauhati 781039 India

The Steiner tree problem is one of the fundamental and classical problems in combinatorial optimization. In this paper we study this problem in the CONGESTED CLIQUE model (CCM) [29] of distributed computing. For the Steiner tree problem in the CCM, we consider that each vertex of the input graph is uniquely mapped to a processor and edges are naturally mapped to the links between the corresponding processors. Regarding output, each processor should know whether the vertex assigned to it is in the solution or not and which of its incident edges are in the solution. We present two deterministic distributed approximation algorithms for the Steiner tree problem in the CCM. The first algorithm computes a Steiner tree using (O) over bar (n(1/3)) rounds and (O) over bar (n(7/3)) messages for a given connected undirected weighted graph of n nodes. Note here that (O) over tilde(.) notation hides polylogarithmic factors in n. The second one computes a Steiner tree using O(S +loglog n) rounds and O(Sm + n(2)) messages, where S and m are the shortest path diameter and number of edges respectively in the given input graph. Both the algorithms achieve an approximation ratio of 2(1 - 1/l), where l is the number of leaf nodes in the optimal Steiner tree. For graphs with S = omega(n(1/3)log n), the first algorithm exhibits better performance than the second one in terms of the round complexity. On the other hand, for graphs with S = (o) over tilde (n(1/3)), the second algorithm outperforms the first one in terms of the round complexity. In fact when S = O(loglog n) then the second algorithm achieves a round complexity of O(loglog n) and message complexity of (O) over tilde (n(2)). To the best of our knowledge, this is the first work to study the Steiner tree problem in the CCM.

关键词： Steiner tree shortest path forest CONGESTED CLIQUE distributed approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved distributed approximation for Steiner tree in the CONGEST model

引用

JOURNAL OF PARALLEL AND distributed COMPUTING 2021年 158卷 196-212页

作者： Saikia, Parikshit Karmakar, Sushanta Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati 781039 India

In this paper we present two deterministic distributed algorithms for the Steiner tree(ST) problem in the CONGEST model. The first algorithm computes a 2(1-1/l)-approximate ST using O(S+ root nlog* n) rounds and O(mS+ n(3/2)) messages for a graph of nnodes and medges, where Sis the shortest path diameter of the graph and l is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is (O) over tilde (S+ root min{St, n})[34], where iota is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O(n(3/2)) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S= O(logn), a 2(1 - 1/l)-approximate ST can be deterministically computed using (O) over tilde(root n) rounds and (O) over tilde (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in[15,22,37]. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Steiner tree distributed approximation algorithm Singularly-optimal

来源：评论

学校读者我要写书评

暂无评论

Round-Message Trade-Off in distributed Steiner Tree Construction in the CONGEST Model 16th

Round-Message Trade-Off in Distributed Steiner Tree Construc...

引用

16th International Conference on distributed Computing and Internet Technology (ICDCIT)

作者： Saikia, Parikshit Karmakar, Sushanta Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati 781039 India

ISBN: (纸本)9783030369873;9783030369866

The Steiner tree problem is one of the fundamental optimization problems in distributed graph algorithms. Recently Saikia and Karmakar [27] proposed a deterministic distributed algorithm for the Steiner tree problem that constructs a Steiner tree in O(S + root n log* n) rounds whose cost is optimal upto a factor of 2(1 - 1/l), where n and S are the number of nodes and shortest path diameter [17] respectively of the given input graph and l is the number of terminal leaf nodes in the optimal Steiner tree. The message complexity of the algorithm is O(Delta(n - t)S + n(3/2)), which is equivalent to O(mS + n(3/2)), where. is the maximum degree of a vertex in the graph, t is the number of terminal nodes (we assume that t < n), and m is the number of edges in the given input graph. This algorithm has a better round complexity than the previous best algorithm for Steiner tree construction due to Lenzen and Patt-Shamir [21]. In this paper we present a deterministic distributed algorithm which constructs a Steiner tree in <(O)over tilde> (S + root n) rounds and (O) over tilde (mS) messages and still achieves an approximation factor of 2(1 - 1/l). Note here that (O) over tilde (center dot) notation hides polylogarithmic factors in n. This algorithm improves the message complexity of Saikia and Karmakar's algorithm by dropping the additive term of O(n(3/2)) at the expense of a logarithmic multiplicative factor in the round complexity. Furthermore, we show that for sufficiently small values of the shortest path diameter (S = O(log n)), a 2(1- 1/l)-approximate Steiner tree can be computed in (O) over tilde (root n) rounds and (O) over tilde (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [9,12,23].

关键词： Steiner tree distributed approximation algorithm Singularly-optimal

来源：评论

学校读者我要写书评

暂无评论

An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs

引用

THEORETICAL COMPUTER SCIENCE 2016年 615卷 102-119页

作者： Kamei, Sayaka Izumi, Tomoko Yamauchi, Yukiko Hiroshima Univ Grad Sch Engn Dept Informat Engn 1-4-1 Kagamiyama Higashihiroshima Hiroshima 7398527 Japan Ritsumeikan Univ Coll Informat Sci & Engn 1-1-1 Noji Higashi Shiga 5258577 Japan Kyushu Univ Grad Sch ISEE Nishi Ku 744 Motooka Fukuoka Fukuoka 8190395 Japan

A connected dominating set (CDS) is useful in forming a virtual backbone in wireless ad hoc or sensor networks because these networks lack a fixed infrastructure and centralized management. Self-stabilization guarantees. that the system tolerates any finite number of transient faults and does not need any initialization. The safe convergence property guarantees that the system quickly converges to a feasible safe configuration, and subsequently converges to a legitimate configuration without violating safety. A previous publication on a safely converging algorithm for the minimum CDS assumed a phase clock synchronizer, which is a very strong assumption. In this paper, we propose the first asynchronous self-stabilizing (6 + epsilon)-approximation algorithm with safe convergence for the minimum CDS in networks modeled by unit disk graphs (UDGs). We assume that the feasible safe configuration satisfies the condition that a dominating set is constructed. The convergence time to a feasible safe configuration is one round, and the convergence time to a legitimate configuration in which an approximated minimum CDS is constructed is O (max{d(2), n}) rounds, and O(n(6)) steps. (c) 2015 The Authors. Published by Elsevier B.V.

关键词： Self-stabilization Safe convergence Minimum connected dominating set Unit disk graph distributed approximation algorithm Unfair distributed daemon

来源：评论

学校读者我要写书评

暂无评论

Semi-asynchronous and distributed weighted connected dominating set algorithms for wireless sensor networks

引用

COMPUTER STANDARDS & INTERFACES 2015年 42卷 143-156页

作者： Dagdeviren, Orhan Erciyes, Kayhan Tse, Savio Ege Univ Int Comp Inst TR-35100 Izmir Turkey Izmir Univ Dept Comp Engn TR-35350 Izmir Turkey Istanbul Univ Dept Comp Engn TR-34320 Istanbul Turkey

Energy-efficient backbone construction is one of the most important objective in a wireless sensor network (WSN) and to construct a more robust backbone, weighted connected dominating sets can be used where the energy of the nodes are directly related to their weights. In this study, we propose algorithms for this purpose and classify our algorithms as weighted dominating set algorithms and weighted Steiner tree algorithms where these algorithms are used together to construct a weighted connected dominating set (WCDS). We provide fully distributed algorithms with semi-asynchronous versions. We show the design of the algorithms, analyze their proof of correctness, time, message and space complexities and provide the simulation results in ns2 environment. We show that the approximation ratio of our algorithms is 3ln(S) where S is the total weight of optimum solution. To the best of our knowledge, our algorithms are the first fully distributed and semi-asynchronous WCDS algorithms with 3ln(S) approximation ratio. We compare our proposed algorithms with the related work and show that our algorithms select backbone with lower cost and less number of nodes. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Wireless sensor networks Weighted connected dominating set distributed approximation algorithm Backbone formation

来源：评论

学校读者我要写书评

暂无评论

An improved distributed data aggregation scheduling in wireless sensor networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2014年第2期27卷 221-240页

作者： Li, Deying Zhu, Qinghua Du, Hongwei Li, Jianzhong Renmin Univ China Sch Informat Beijing 100872 Peoples R China Harbin Inst Technol Shenzhen Grad Sch Shenzhen 518055 Peoples R China Harbin Inst Technol Sch Comp Sci & Technol Harbin 150001 Peoples R China

This paper focuses on the distributed data aggregation collision-free scheduling problem, which is one of very important issues in wireless sensor networks. Bo et al. (Proc. IEEE INFOCOM, 2009) proposed an approximate distributed algorithm for the problem and Xu et al. (Proc. ACM FOWANC, 2009) proposed a centralized algorithm and its distributed implementation to generate a collision-free scheduling for the problem, which are the only two existing distributed algorithms. Unfortunately, there are a few mistakes in their performance analysis in Bo et al. (Proc. IEEE INFOCOM, 2009), and the distributed algorithm can not get the same latency as the centralized algorithm because the distributed implementation was not an accurate implementation of the centralized algorithm (Xu et al. in Proc. ACM FOWANC, 2009). According to those, we propose an improved distributed algorithm to generate a collision-free schedule for data aggregation in wireless sensor networks. Not an arbitrary tree in Bo et al. (Proc. IEEE INFOCOM, 2009) but a breadth first search tree (BFS) rooted at the sink node is adopted, the bounded latency 61R+5 Delta-67 of the schedule is obtained, where R is the radius of the network with respect to the sink node and Delta is the maximum node degree. We also correct the latency bound of the schedule in Bo et al. (Proc. IEEE INFOCOM, 2009) as 61D+5 Delta-67, where D is a diameter of the network and prove that our algorithm is more efficient than the algorithm (Bo et al. in Proc. IEEE INFOCOM, 2009). We also give a latency bound for the distributed implementation in Xu et al. (Proc. ACM FOWANC, 2009).

关键词： distributed approximation algorithm Data aggregation scheduling Collision-free Latency Wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

A fast distributed approximation algorithm for minimum spanning trees

引用

distributed COMPUTING 2008年第6期20卷 391-402页

作者： Khan, Maleq Pandurangan, Gopal Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time (O) over tilde (D(G)+L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Omega(D(G) + L(G, w)) time to compute an H-approximation to the MST for any H is an element of [1, Theta(log n)]. Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal (O) over tilde (D(G)) time.

关键词： minimum spanning tree distributed approximation algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A fast distributed approximation algorithm for minimum spanning trees

引用

20th International Symposium on distributed Computing

作者： Khan, Maleq Pandurangan, Gopal Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

ISBN: (纸本)3540446249

关键词： minimum spanning tree distributed approximation algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks

引用

INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS 2005年第8期18卷 743-762页

作者： Gao, B Yang, YH Ma, HY Shanghai Jiao Tong Univ Dept Elect Engn Shanghai 200030 Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub-graph. However, finding the minimum connected dominating set (MCDS) is a well-known NP-hard problem in graph theory. approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one-hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright (c) 2005 John Wiley & Sons, Ltd.

关键词： ad hoc networks distributed approximation algorithm connected dominating set maximal independent set

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：