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

8th SIAM Symposium on Simplicity of algorithms, SOSA 2025

作者： Björklund, Andreas Husfeldt, Thore IT University of Copenhagen Denmark

ISBN: (纸本)9781611978315

We consider the parameterised k, e-Long Cycle problem, in which you are given an n-vertex undirected graph G, a specified edge e in G, and a positive integer k, and are asked to decide if the graph G has a simple cycle through e of length at least k. We show how to solve the problem in 1.731k poly(n) time, improving over the 2k poly(n) time algorithm by [Fomin et al., TALG 2024], but not the more recent 1.657k poly(n) time algorithm by [Eiben, Koana, and Wahlström, SODA 2024]. When the graph is bipartite, we can solve the problem in 2k/2 poly(n) time, matching the fastest known algorithm for finding a cycle of length exactly k in an undirected bipartite graph [Björklund et al., JCSS 2017]. Our results follow the approach taken by [Fomin et al., TALG 2024], which describes an efficient algorithm for finding cycles using many colours in a vertex-coloured undirected graph. Our contribution is twofold. First, we describe a new algorithm and analysis for the central colourful cycle problem, with the aim of providing a comparatively short and self-contained proof of correctness. Second, we give tighter reductions from k, e-Long Cycle to the colourful cycle problem, which lead to our improved running times. Copyright © 2025 Copyright for this paper is retained by authors.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Bipartite Domination in Graphs: Complexity and algorithms 11th

Bipartite Domination in Graphs: Complexity and Algorithms

引用

11th International Conference on algorithms and Discrete Applied Mathematics, CALDAM 2025

作者： Panda, Bhawani Sankar Joshi, Subhasmita Jacob, Dalu Department of Computer Science and Engineering The LNM Institute of Information Technology Jaipur302031 India Department of Mathematics Indian Institute of Technology Delhi Hauz Khas New Delhi110016 India

ISBN: (纸本)9783031834370

A set D⊆V of vertices of a graph G=(V,E) is called a dominating set of G if for every vertex u∈V\D, there exists a vertex v∈D such that uv∈E(G). A dominating set D is called a bipartite dominating set if G[D], the subgraph induced by D, is bipartite. The domination number of G is the minimum cardinality among all dominating sets of G and it is denoted by γ(G). The bipartite domination number of G is the minimum cardinality among all bipartite dominating sets of G and it is denoted by γbip(G). The Min Dom problem is to find a dominating set of minimum cardinality of a given graph G and Decide Dom is the decision version of the Min Dom problem. Similarly, the Min Bip-Dom problem is to find a bipartite dominating set of minimum cardinality of a given graph G and Decide Bip-Dom is the decision version of the Min Bip-Dom problem. In this paper, we initiate the algorithmic study of the Min Bip-Dom problem. First, we study the complexity difference between the Min Dom problem and the Min Bip-Dom problem. The difference between γbip(G) and γ(G) of a graph G can be arbitrarily large. However, the Decide Bip-Dom problem is the same as the Decide Dom problem for bipartite graphs and hence is NP-complete for bipartite graphs, as Decide Dom problem is known to be NP-complete for bipartite graphs. We show that Decide Bip-Dom is NP-complete for non-bipartite graphs as well. Finally, we propose polynomial-time algorithms for the Min Bip-Dom problem for interval graphs and block graphs. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Fine-Grained Complexity of Approximating Max k-Coverage 18th

On the Fine-Grained Complexity of Approximating Max k-Cove...

引用

18th International Joint Conference on Theoretical Computer Science-Frontier of algorithmic Wisdom, IJTCS-FAW 2024

作者： Wang, Haoqi Nanjing University Nanjing China

ISBN: (纸本)9789819777518

The max k-coverage problem asks us to select k subsets from a collection S of subsets of a universe U, such that the union of these k subsets covers as many elements of U as possible. We prove that for every λ∈(0,1) and k∈N, there exists an algorithm which, given a max k-coverage instance with input size N, finds k sets that cover at least (1-1/e+λ/e)·opt elements for max k-coverage in O(Nλk+O(1))-time, where opt is the number of elements covered by the optimal solution. On the other hand, we show that, assuming the Gap Exponential Time Hypothesis, while λ is a constant, the fastest (1-1/e+λ)-approximation algorithm for max k-coverage running in O(Nαk+o(1)) time satisfies α≥Ω(λ4). While non constant λ=λ(k) is a small function of k, the fastest (1-1/e+λ)-approximation for max k-coverage running in time O(Nαk+o(1)) satisfies α≥Ω(λ1λ). © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Decentralized Learning with Approximate Finite-Time consensus

arXiv

引用

arXiv 2025年

作者： Fainman, Aaron Vlaski, Stefan Department of Electrical and Electronic Engineering Imperial College London United Kingdom

The performance of algorithms for decentralized optimization is affected by both the optimization error and the consensus error, the latter of which arises from the variation between agents’ local models. Classically, algorithms employ averaging and gradient-tracking mechanisms with constant combination matrices to drive the collection of agents to consensus. Recent works have demonstrated that using sequences of combination matrices that achieve finite-time consensus (FTC) can result in improved communication efficiency or iteration complexity for decentralized optimization. Notably, these studies apply to highly structured networks, where exact finite-time consensus sequences are known exactly and in closed form. In this work we investigate the impact of utilizing approximate FTC matrices in decentralized learning algorithms, and quantify the impact of the approximation error on convergence rate and steady-state performance. Approximate FTC matrices can be inferred for general graphs and do not rely on a particular graph structure or prior knowledge, making the proposed scheme applicable to a broad range of decentralized learning settings. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

A High Utility Co-location Pattern Mining algorithm Using Multiple Utility Thresholds 25th

A High Utility Co-location Pattern Mining Algorithm Using Mu...

引用

25th International Conference on Web Information Systems Engineering, WISE 2024

作者： Tran, Vanha Bui, Thiloan Do, Thaigiang Le, Hoangan FPT University Hanoi155514 Viet Nam

ISBN: (纸本)9789819605781

High utility co-location pattern (HUCP) mining refers to discovering a group of spatial features from spatial data which the instances of the group are neighbors in space and have high utility values. Currently, existing algorithms use a unique minimum utility threshold to filter HUCPs, but instance utility values and instance numbers of features in datasets vary greatly, thus it is not fair to compare all features with a unique threshold, which can easily filter out some interesting patterns. This paper proposes an algorithm for mining HUCPs based on multiple utility thresholds to void this issue. Users set a utility threshold for each feature according to their application field. The threshold of a pattern is adaptively determined by the features involved in it, i.e., the minimum threshold of these features that participate in the pattern. Moreover, to avoid repeatedly verifying the neighboring relationships between instances when collecting participating instances of each pattern, this paper adopts a mining method that uses maximal cliques and a hash table structure. First, neighboring instances are enumerated only once by maximal cliques and put into a close-packed hash structure. Then, the instances of features that participate in any patterns are queried from this structure without repeatedly verifying neighbor relationships. The designed algorithm is experimentally assessed on both synthetic and real-world spatial data. The results prove that the designed algorithm is more effective and efficient than existing algorithms. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Experimental validation of consensus algorithms for multivehicle cooperative control

引用

IEEE TRANSACTIONS ON CONTROL SYSTEMS TECHNOLOGY 2008年第4期16卷 745-752页

作者： Ren, Wei Chao, Haiyang Bourgeous, William Sorensen, Nathan Chen, YangQuan Utah State Univ Dept Elect & Comp Engn Logan UT 84322 USA

In this brief, consensus algorithms are experimentally implemented and validated on a mobile actuator and sensor network platform under directed, possibly switching interaction topologies to explore issues and challenges in distributed multivehicle cooperative control. Distributed consensus algorithms are applied to two target applications including rendezvous and axial alignment. In the rendezvous application, multiple mobile robots simultaneously arrive at a common a priori unknown target location determined through team negotiation. In the axial alignment application, multiple mobile robots collectively align their final positions along a line. The experimental results show the effectiveness and robustness of the consensus algorithms even in the presence of platform physical limitations, packet loss, information delay, etc. These experimental results validate the corresponding theoretical results.

关键词： axial alignment cooperative control consensus algorithm mobile actuator and sensor network multivehicle systems rendezvous

来源：评论

学校读者我要写书评

暂无评论

Optimal Frequency Control for Inverter-Based Micro-Grids Using Distributed Finite-Time consensus algorithms

引用

IEEE ACCESS 2020年 8卷 185243-185252页

作者： Cao, Qian Xie, Weicheng Chongqing Univ Sch Automat Chongqing 401331 Peoples R China Xihua Univ Sch Elect Engn Chengdu 610039 Peoples R China

This paper addresses the distributed frequency control and economic dispatch problem of micro-grid systems. The optimal frequency control problem is formulated considering both frequency regulation and generation cost minimization, by establishing an equivalent nonlinear second-order dynamic model. A distributed finite-time consensus protocol is proposed to solve the optimal frequency regulation problem based on the equivalent model. Despite the nonlinear dynamics, the system frequency converges to the nominal value and the economic dispatch is achieved both in finite time. It is proved that the equilibrium point of the closed-loop system is the unique optimal solution to the associated economic dispatch problem. Simulation results verify the theoretical analysis and demonstrate the effectiveness of the proposed control method.

关键词： Frequency control Economics Generators Convergence Power generation Heuristic algorithms consensus algorithm Distributed finite-time control frequency control economic dispatch problem micro-grid hierarchical control

来源：评论

学校读者我要写书评

暂无评论

CEV Framework: A Central Bank Digital Currency Evaluation and Verification Framework With a Focus on consensus algorithms and Operating Architectures

引用

IEEE ACCESS 2022年 10卷 63698-63714页

作者： Jin, Si Yuan Xia, Yong HSBC Lab Guangzhou 510440 Peoples R China

We propose a Central Bank Digital Currency Evaluation and Verification (CEV) Framework for recommending and verifying technical solutions in the central bank digital currency (CBDC) system. We demonstrate two sub-frameworks: an evaluation sub-framework that provides consensus algorithm and operating architecture solutions and a verification sub-framework that validates the proposed solutions. Our framework offers a universal CBDC solution that is compatible with different national economic and regulatory regimes. The evaluation sub-framework generates customized solutions by splitting the consensus algorithms into several components and analyzing their impacts on CBDC systems. CBDC design involves a trade-off between system features - the consensus algorithm cannot achieve all system features simultaneously. However, we also improve the operating architectures to compensate for the weak system features. The verification sub-framework helps verify our proposed solution through empirical experiments and formal proof. Our framework offers CBDC designers the flexibility to iteratively tune the trade-off between CBDC system features for the desired solution. To the best of our knowledge, we are the first to propose a framework to recommend and verify CBDC technical solutions.

关键词： consensus algorithm Business Blockchains Privacy Online banking Scalability Licenses Central bank digital currency evaluation sub-framework consensus algorithm operating architectures verification sub-framework

来源：评论

学校读者我要写书评

暂无评论

Evaluating Network Structures in Byzantine-based consensus algorithms for Sarawak's Digitalized Pepper Value Chain

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2024年第5期40卷 943-955页

作者： Kueh, Feng-Yi Tang, Fu-Ee Ling, Huo-Chong Tan, Yee-Yong Ho, Carrie Lee-Ing Curtin Univ Dept Elect & Comp Engn Miri 98009 Malaysia Curtin Univ Dept Civil & Construct Engn Miri 98009 Malaysia RMIT Univ Sch Sci Engn & Technol Ho Chi Minh City 70000 Vietnam

Known as the "King of Spice", pepper (Piper nigrum) is the most widely used and traded agricultural product in the world. In Sarawak, pepper is listed as the few industrial crops in producing and contributing the most to the gross domestic product (GDP) of the country, Malaysia. However, the recent price fluctuation in the global pepper market has caused some farmers to abandon pepper farms due to the lower pepper prices against the high cost of input materials and farm maintenance, in addition to limited marketing choices and bargaining power when dealing with buyers due to their geographic remoteness, small production quantity, and variable product. To improve the circumstances, the use of block- chain technology with Byzantine-based consensus algorithm is proposed in this paper to minimize some of the constraints faced by the smallholder farmers. With the PBFT consensus algorithm on-board, the blockchain network (BCN) operates without miners as it relies on the message-transfer mechanism to achieve the total consensus. Besides, the PBFT consensus algorithm with varying network structures were evaluated. Upon comparison between network structures, the group network structure dominated the entirety of the experiment and presented as the proposed network structure, with the addition of specific nodes such as relay, storage, administer and brackets: bench and penalty to facilitate and maintain the longevity of the BCN. The implementation of blockchain technology in Sarawak's pepper industry has the potential to improve the linkages and cohesion between pepper stakeholders but its overall integration would have to be further explored.

关键词： blockchain technology consensus algorithm linkages network structures pe- pper Sarawak stakeholders

来源：评论

学校读者我要写书评

暂无评论

Cluster-Based Classification of Blockchain consensus algorithms

引用

IEEE LATIN AMERICA TRANSACTIONS 2021年第4期19卷 688-696页

作者： Aponte, Fredy Gutierrez, Luz Pineda, Magda Merino, Ines Salazar, Augusto Wightman, Pedro Univ Santo Tomas Barranquilla Colombia Univ Norte Barranquilla Atlantico Colombia Univ Magdalena Santa Marta Colombia

In recent years, Blockchain has become a disruptivetechnology to protect the integrity of information, especially inopen and collaborative information systems. Its main advantageis the possibility to reach consensus on the new data blocks tobe added to the chain, even with anonymous actors. The mostcommon consensus mechanism is Proof of Work, but it has beenproven to be very inefficient in terms of energy spent by themembers of the blockchain. In the literature there are many othertechniques that pretend to become the new popular ***, the number of this techniques is growing too fast toreally be able to differentiate among all the options. In this work,a new characterization of consensus algorithm is proposed, thatcan be used to find families of mechanism using cluster-basedclassification. Using the Ward Method and Spearmans RankCorrelation analysis, new clusters of consensus mechanisms wereidentified. The results describe the behavioral patterns not seenbefore in the literature. In addition, some open problems ofcurrent consensus algorithms are discussed.

关键词： Blockchain Proof of Work Fault tolerant systems Fault tolerance Distributed ledger Scalability consensus algorithm Blockchain Cluster-based classification consensus algorithms Proof of Work Spearman Rank Correlation Ward Method

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：