A Greedy Algorithm for Constructing Region-Fault Tolerant Geometric Spanners
Journal Title: Electronic and Cyber Defense - Year 2023, Vol 10, Issue 4
Abstract
In this paper, we consider the problem of constructing the region-fault tolerant geometric spanners when the problem is restricted to a subclass of convex regions. Let S be a set of n points in the plane. In particular, in this paper, a greedy algorithm for constructing the region-fault tolerant geometric spanner of S where the region faults are a set of at most k half-planes with parallel boundaries is presented. We show that the proposed algorithm has the time complexity O(kn^3 logâ¡n ), and the generated graph contains O(kn) edges. To the best of our knowledge, the best-known algorithm to construct the region-fault tolerant geometric spanner of S takes O(n log^2â¡n) time and the generated graph has O(n logâ¡n) edges.
Authors and Affiliations
Davood Bakhshesh,Mohammad Farshi,
Keywords
Related Articles
- EP ID EP731686
- DOI -
- Views 37
- Downloads 0
Security of UAV Relay Networks based on Covert Communication in the Presence of an Eavesdropping UAV
This paper proposes the use of a trusted decoder and forward (DF) Unmanned Aerial Vehicle (UAV) relay to establish a covert communication between a terrestrial transmitter (Alice) and a receiver (Bob), which is located i...
A way to predict the stock price of the Tehran Stock Exchange in relation to knowledge
In recent years, due to the profitability of the stock market in Iran, small and large investments were attracted to this market, but unfortunately, due to their lack of knowledge of the stock market and price forecastin...
Distributed Solving of Weapon Target Assignment Problem using Learning Automata
This article presents a method to solve the weapon target assignment problem, which is one of the problems of distributed constraint optimization. The previous methods do not guarantee the convergence problem properly an...
Mobile botnets detection using deep learning techniques
Smartphones are now well integrated with advanced capabilities and technologies such as the Internet. Today, due to the facilities and capabilities and the widespread use of smart mobile devices, mobile security has beco...
A Trust Evaluation Model for Cloud Computing Using Bayesian Network
In recent years, cloud computing has attracted much attention as a new computing model for providing infrastructure, platform, and software as a service. There is an important challenge in trust management between cloud...