Electrical and Electronic Engineering - Research Publications
Permanent URI for this collection
Search Results
1 - 10 of 17
-
ItemNo Preview AvailableNetwork augmentation for disaster-resilience against geographically correlated failure(WILEY, 2023-06)Abstract We introduce a formal framework for the study of augmenting networks in the plane for disaster‐resilience, where a disaster is modeled by a straight‐line segment. We generalize various graph structures from classical 2‐edge‐connectivity, including minimal cuts and blocks. The key concept that we introduce is that of an ‐leaf, which builds on the fundamental “leaf‐block” concept from classical augmentation. We present a number of algorithms for constructing the above‐mentioned graph structures, including a sweep‐line algorithm that finds all edge‐cuts that can be destroyed by a single disaster. We also present an algorithm which optimally adds a single edge between a pair of ‐leaves or blocks while avoiding certain disaster regions. Finally, we present a number of heuristic schemes for solving the disaster‐resilient network augmentation problem and perform extensive experiments to demonstrate the power of the ‐leaf concept within heuristic design.
-
ItemComputing minimum 2-edge-connected Steiner networks in the Euclidean plane(WILEY, 2019-01)Abstract We present a new exact algorithm for computing minimum 2‐edge‐connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2‐edge‐connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals—doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2‐edge‐connected Steiner network problem.
-
ItemMinimum Steiner trees on a set of concyclic points and their center(WILEY, 2022-07)Abstract Consider a configuration of points comprising a point q and a set of concyclic points R that are all a given distance r from q in the Euclidean plane. In this paper, we investigate the relationship between the length of a minimum Steiner tree (MStT) on and a minimum spanning tree on R. We show that if the degree of q in the MStT is 1, then the difference between these two lengths is at least , and that this lower bound is tight. This bound can be applied as part of an efficient algorithm to find the solution to the prize‐collecting Euclidean Steiner tree problem, as outlined in an earlier paper.
-
ItemCurvature-constrained directional-cost paths in the plane(SPRINGER, 2012-08)
-
ItemGradient-Constrained Minimum Networks. III. Fixed Topology(SPRINGER/PLENUM PUBLISHERS, 2012-10)
-
ItemMaximizing the net present value of a Steiner tree(Springer US, 2015)The theory of Steiner trees has been extensively applied in physical network design problems to locate a Steiner point that minimizes the total length of a tree. However, maximizing the total generated cash flows of a tree has not been investigated. Such a tree has costs associated with its edges and values associated with nodes. In order to reach the nodes in the tree, the edges need to be constructed. The edges are constructed in a particular order and the costs of constructing the edges and the values at the nodes are discounted over time. These discounted costs and values generate cash flows. In this paper, we study the problem of optimally locating a single Steiner point so as to maximize the sum of all the discounted cash flows, known as the net present value (NPV). An application of this problem occurs in underground mining where, we want to optimally locate a junction point in the underground access network to maximize the NPV. We propose an efficient iterative algorithm to optimally locate a single degree-3 Steiner point. We show this algorithm converges quickly and the Steiner point is unique subject to realistic design parameters.
-
ItemOn the history of the Euclidean Steiner tree problem(SPRINGER, 2014-05)
-
ItemOptimal curvature-constrained paths for general directional-cost functions(SPRINGER, 2013-09)
-
Item
-
ItemSimplifying obstacles for Steiner network problems in the plane(WILEY, 2022-07)Abstract We present methods for simplifying the geometry of polygonal obstacles as a preprocessing step to solving obstacle‐avoiding Steiner network problems in the plane. The methods reduce the total number of vertices and edges that need to be considered for the given obstacles, and their use is expected to significantly improve the efficiency of exact algorithms for solving a range of practical Steiner network problems in obstacle environments. Included are methods for extending obstacles (via a new padding method and a backfilling procedure from the literature), and various methods for simplifying obstacles, including new methods called bounding and eliminating. We show that these methods reduce the total number of obstacle vertices and edges by performing experiments on obstacles with up to 100 vertices in the presence of up to 100 terminals. The experiments utilize a modified version of a known algorithm for quickly generating large numbers of “random” polygons with hundreds of vertices. Corresponding datasets and implementations have been made available on GitHub.