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

Dynamic key distribution method for wireless sensor networks based on exponential algorithm

INTERNATIONAL JOURNAL OF AUTONOMOUS AND ADAPTIVE COMMUNICATIONS SYSTEMS 2023年第1期16卷 97-111页

作者： Zhao, Yun Xiao, Yong Lin, Weibin Cui, Chao Xu, Di Elect Power Res Inst China Southern Power Grid Guangzhou 510080 Peoples R China

The purpose of this paper is to overcome the problems of high communication failure probability, high energy cost, low global connectivity and poor network robustness, a dynamic key distribution method based on exponential algorithm is proposed. In this method, the collusion characteristics of newly added nodes and revoked nodes in wireless sensor networks are used to establish a wireless sensor security model. The exponential algorithm is used to initialise, broadcast, self repair session key and mutual session key It can help repair, add nodes and cancel nodes to realise dynamic key distribution. The experimental results show that when the number of dynamic key nodes is 600, the probability of communication failure is 47%;when the number of hops is 10, the energy cost is only 1.64 mJ, and the network robustness is high. It reduces the pressure of wireless sensor network and plays a positive role in the root cause location of massive alarm information fault.

关键词： exponential algorithm wireless sensor network dynamic key distribution method

来源：评论

学校读者我要写书评

暂无评论

Many-visits TSP revisited

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 124卷 112-128页

作者： Kowalik, Lukasz Li, Shaohua Nadara, Wojciech Smulewicz, Marcin Wahlstrom, Magnus Univ Warsaw Inst Informat Warsaw Poland Royal Holloway Univ London Egham Surrey England

We study the MANY-VISITS TRAVELING SALESMAN PROBLEM, where given a number k(v) for each of n cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city v exactly k(v) times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [ SODA 2019, TALG 2020] and runs in time and space O* (5(n)). They also show a polynomial-space algorithm running in time O (16(n+o(n))). In this work, we show three main results: A randomized polynomial-space algorithm running in time O* (2(n)D), where D is the maximum distance between two cities. By using standard methods, this results in a (1 + is an element of)-approximation running in time O*(2(is an element of)(n)(-1)). A tight analysis of Berger et al.'s exponential-space algorithm, resulting in an O*(4(n)) running time bound. A new polynomial-space algorithm, running in time O(7.88(n)). (C) 2021 The Author(s). Published by Elsevier Inc.

关键词： Many-visits traveling salesman problem exponential algorithm

来源：评论

学校读者我要写书评

暂无评论

Exact and approximate bandwidth

引用

THEORETICAL COMPUTER SCIENCE 2010年第40-42期411卷 3701-3713页

作者： Cygan, Marek Pilipczuk, Marcin Univ Warsaw Dept Math Comp Sci & Mech PL-02097 Warsaw Poland

In this paper we gather several improvements in the field of exact and approximate exponential time algorithms for the BANDWIDTH problem. For graphs with treewidth t we present an O(n(0(t))2(n)) exact algorithm. Moreover, for any two positive integers k >= 2, r >= 1, we present a (2kr - 1)-approximation algorithm that solves BANDWIDTH for an arbitrary input graph in O*(k(n/(k-1)r)) time and polynomial space where by O* we denote the standard big O notation but omitting polynomial factors. Finally, we improve the currently best known exact algorithm for arbitrary graphs with an O(4.383(n)) time and space algorithm. In the algorithms for the small treewidth we develop a technique based on the Fast Fourier Transform, parallel to the Fast Subset Convolution techniques introduced by Bjorklund et al. This technique can be also used as a simple method of finding a chromatic number of all subgraphs of a given graph in O*(2(n)) time and space, what matches the best known results. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Bandwidth exponential algorithm Exact algorithm Approximate algorithm Graph

来源：评论

学校读者我要写书评

暂无评论

On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized Perspective

引用

THEORY OF COMPUTING SYSTEMS 2024年第1期68卷 122-143页

作者： Mkrtchyan, Vahan Petrosyan, Garik Subramani, K. Wojciechowski, Piotr Gran Sasso Sci Inst Sch Adv Studies Laquila Italy Yerevan State Univ Dept Informat & Appl Math Yerevan Armenia West Virginia Univ LDCSEE Morgantown WV 26506 USA

In this paper, we examine variants of the partial vertex cover problem from the perspective of parameterized algorithms. Recall that in the classical vertex cover problem (VC), we are given a graph G = < V, E > and a number k and asked if we can cover all of the edges in E, using at most k vertices from V. The partial vertex cover problem (PVC) is a more general version of the VC problem in which we are given an additional parameter k'. We then ask the question of whether at least k' of the edges in E can be covered using at most k vertices from V. Note that the VC problem is a special case of the PVC problem when k' = vertical bar E vertical bar. In this paper, we study the weighted generalizations of the PVC problem. This is called the weighted partial vertex cover problem (WPVC). In the WPVC problem, we are given two parameters R and L, associated respectively with the vertex set V and edge set E of the graph G respectively. Additionally, we are given non-negative integral weight functions for the vertices and the edges. The goal then is to cover edges of total weight at least L, using vertices of total weight at most R. This paper studies several variants of the PVC and WPVC problems and establishes new results from the perspective of fixed-parameter tractability and W[1]-hardness. We also introduce a new problem called the partial vertex cover with matching constraints and show that it is Fixed-Parameter Tractable (FPT) for a certain class of graphs. Finally, we show that the WPVC problem is APX-complete for bipartite graphs.

关键词： Partial vertex cover Weighted partial vertex cover Bipartite graph exponential algorithm Fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Variants of Non-Negative Least-Mean-Square algorithm and Convergence Analysis

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2014年第15期62卷 3990-4005页

作者： Chen, Jie Richard, Cedric Bermudez, Jose-Carlos M. Honeine, Paul Univ Nice Sophia Antipolis CNRS Cote dAzur Observ F-06108 Nice 2 France Univ Fed Santa Catarina Dept Elect Engn BR-88040900 Florianopolis SC Brazil Univ Technol Troyes CNRS Inst Charles Delaunay F-10010 Troyes France

Due to the inherent physical characteristics of systems under investigation, non-negativity is one of the most interesting constraints that can usually be imposed on the parameters to estimate. The Non-Negative Least-Mean-Square algorithm (NNLMS) was proposed to adaptively find solutions of a typical Wiener filtering problem but with the side constraint that the resulting weights need to be non-negative. It has been shown to have good convergence properties. Nevertheless, certain practical applications may benefit from the use of modified versions of this algorithm. In this paper, we derive three variants of NNLMS. Each variant aims at improving the NNLMS performance regarding one of the following aspects: sensitivity of input power, unbalance of convergence rates for different weights and computational cost. We study the stochastic behavior of the adaptive weights for these three new algorithms for non-stationary environments. This study leads to analytical models to predict the first and second order moment behaviors of the weights for Gaussian inputs. Simulation results are presented to illustrate the performance of the new algorithms and the accuracy of the derived models.

关键词： Adaptive signal processing convergence analysis exponential algorithm least-mean-square algorithms non-negativity constraints normalized algorithm sign-sign algorithm

来源：评论

学校读者我要写书评

暂无评论

Trees having many minimal dominating sets

引用

INFORMATION PROCESSING LETTERS 2013年第8期113卷 276-279页

作者： Krzywkowski, Marcin Gdansk Univ Technol Fac Elect Telecommun & Informat PL-80233 Gdansk Poland

We disprove a conjecture by Skupien that every tree of order n has at most 2(n/2) minimal dominating sets. We construct a family of trees of both parities of the order for which the number of minimal dominating sets exceeds 1.416(n). We also provide an algorithm for listing all minimal dominating sets of a tree in time O(1.4656(n)). This implies that every tree has at most 1.4656(n) minimal dominating sets. (c) 2013 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems Minimal dominating set Tree Combinatorial bound exponential algorithm Listing algorithm

来源：评论

学校读者我要写书评

暂无评论

On the number of 2-packings in a connected graph

引用

DISCRETE MATHEMATICS 2012年第23期312卷 3444-3450页

作者： Junosza-Szaniawski, Konstanty Rzazewski, Pawel Warsaw Univ Technol Fac Math & Informat Sci PL-00661 Warsaw Poland

By a 2-packing in a graph we mean a subset of its vertex set, in which all the vertices are in distance at least 3 from each other. The question about the maximum number of 2-packings in a graph is strongly related to the problem of L(2. 1)-labeling of graphs. In this paper we find new asymptotic upper and lower bounds on the maximum number of 2-packings in a connected graph on n vertices. The bounds are 0(1.5399 ... (n)) and Omega(1.4970 ... (n)), respectively. Moreover, we present a lower bound on the number of k-element 2-packings in a connected graph, which is max ((n-2k+2 / k (k + 1) (left perpendicularn-1/2 krightperpendicular)). (C) 2012 Elsevier B.V. All rights reserved.

关键词： 2-packing exponential algorithm Extremal graph theory

来源：评论

学校读者我要写书评

暂无评论

A New Direction for Counting Perfect Matchings

A New Direction for Counting Perfect Matchings

引用

IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

作者： Izumi, Taisuke Wadayama, Tadashi Nagoya Inst Technol Grad Sch Engn Nagoya Aichi Japan

ISBN: (纸本)9781467343831

In this paper, we present a new exact algorithm for counting perfect matchings, which relies on neither inclusion-exclusion principle nor tree-decompositions. For any bipartite graph of 2n nodes and Delta n edges such that Delta >= 3, our algorithm runs with O*(2((1-1/O(Delta log Delta))n)) time and exponential space. Compared to the previous algorithms, it achieves a better time bound in the sense that the performance degradation to the increase of Delta is quite slower. The main idea of our algorithm is a new reduction to the problem of computing the cut-weight distribution of the input graph. The primary ingredient of this reduction is MacWilliams Identity derived from elementary coding theory. The whole of our algorithm is designed by combining that reduction with a non-trivial fast algorithm computing the cut-weight distribution. To the best of our knowledge, the approach posed in this paper is new and may be of independent interest.

关键词： counting perfect matchings exponential algorithm coding theory MacWilliams identity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：