China
Africa
Explore chapters and articles related to this topic
Data Gathering Algorithms for Wireless Sensor Networks
Published in Shafiullah Khan, Al-Sakib Khan Pathan, Nabil Ali Alrajeh, Wireless Sensor Networks, 2016
Stage 1 of the algorithm can be run in O(|V| + |E| + |V|*log|V|) = O(|E| + |V|*log|V|) time if the Priority-Queue is implemented as a binary heap [10]. If implemented using arrays, this stage of the algorithm takes O(|V| + |E| + |V|2) = O(|E| + |V|2) time. Figure 13.7 illustrates an example for the construction of the ECDS and the ECDS-DG tree. The integer outside a circle represents the node ID, and the real number inside the circle represents the available energy at the node. As can be seen in the iteration 2 of this example, a covered node that has the largest remaining energy (node 25 with 5.6 J) may not be still included into the ECDS if the node has no uncovered neighbors; instead, we consider the covered node that has the next largest remaining energy (node 22 with 5.4 J) and include it into the ECDS as it can cover at least one uncovered node.
Trees and Cycles
Published in Kenneth H. Rosen, Graphs, Algorithms, and Optimization, 2005
The Cheriton-Tarjan algorithm is a modification of Kruskal’s algorithm designed to reduce the O(ε log ε) term. It also grows a spanning forest, beginning with a forest of n — |G| components each consisting of a single node. Now the term O(ε log ε) comes from selecting the minimum edge from a heap of ε edges. Since every component Tu must eventually be connected to another component, this algorithm keeps a separate heap PQu for each component Tu, so that initially n smaller heaps are used. Initially, PQu will contain only Deg(u) edges, since Tu consists only of vertex u. When Tu and Tv are merged, PQu and PQV must also be merged. This requires a modification of the data structures, since heaps cannot be merged efficiently. This is essentially because merging heaps reduces to building a new heap. Any data structure in which a minimum element can be found efficiently is called a priority queue. A heap is one form of priority queue, in which elements are stored as an array, but viewed as a binary tree. There are many other forms of priority queue. In this algorithm, PQu will stand for a priority queue which can be merged. The Cheriton-Tarjan algorithm can be described as follows.
Introduction
Published in Randall L. Eubank, Ana Kupresanin, Statistical Computing in C++ and R, 2011
Randall L. Eubank, Ana Kupresanin
The simplest efficient implementation of a priority queue uses the data structure called a heap. A heap is a binary tree that at each node stores a member of the set and satisfies the properties every node has two children, except for the nodes in the lowest two levels of the tree,the lowest level of the tree is filled left to right (see Figure 9.1) andthe key value of every node is no greater than that of either of its children (known as the heap property).
An efficient algorithm for solving the median problem on real road networks
Published in Engineering Optimization, 2020
Saeed Ghanbartehrani, J. David Porter
The maximum number of iterations performed by the MTD algorithm in the worst case scenario is k.|E|, since an independent search is performed from each demand point. At each iteration, a node is removed and expanded from the open list. These operations have a time complexity of O(log|V|), assuming the heap implementation for priority queues. Other operations, such as adding items to open lists, would also have the same time complexity of O(log|V|). Therefore, the resulting time complexity of the MTD algorithm is O(k.|E|.log|V|).