Models, Algorithms, and Technologies for Network Analysis by Boris Goldengorin Valery A. Kalyagin & Panos M. Pardalos
Author:Boris Goldengorin, Valery A. Kalyagin & Panos M. Pardalos
Language: eng
Format: epub
Publisher: Springer New York, New York, NY
After the root finds and , a subgraph is formed by removing all vertices in and , along with all associated edges. All the nodes from both sets can move and will become descendants of at least one node in according to the algorithms described below.
4.1 Optimal Algorithm
For a root to achieve an optimal achievable topology, it essentially has to consider all possible tree topologies and select the final topology based on the achievable tree that gives the minimum aggregate data traffic. In this section, we provide details about how the optimal solution can be found, subject to the constraint that the topology is reorganized around a preselected root. We use the branch-and-bound technique to limit the complexity of this combinatorial search.
As described above, the root first obtains the active and passive moving node sets using Algorithm 2, as well as the subgraph of nonmoving nodes. A brute-force solution is for the root to consider all nodes in the active moving node set and to evaluate the aggregate data traffic for all achievable tree topologies such that . All achievable tree topologies can be achieved by applying the concept of Prufer code sequence [1, 21]. Each unique Prufer code sequence can be used to represent unique spanning trees. Each unique tree topology with n-labeled nodes can be encoded to obtain a unique Prufer code sequence p of length n − 2, where each element in p is obtained from the set of n node labels. Likewise, each unique Prufer code sequence p of length n − 2 can be decoded to obtain unique tree topology with n labeled nodes. Hence, there exits n n − 2 unique Prufer code sequences p of length n − 2 that can be decoded to obtain n n − 2 unique tree topologies with n label nodes and vice versa.
To obtain all achievable tree topologies such that , subgraph is first contracted into a single node . A set containing all possible Prufer sequences p is then generated from a set of nodes including , , and . Each unique tree topology can be obtained by decoding each . Still more than one possible unique tree for each Prufer sequence may exist since a node always contained in has to be extracted as subgraph to achieve at least one unique graph .
To achieve all unique tree topologies from each , an edge set that contains the edges that are incident to in is first considered. Here v denotes a root of subtree and therefore is connected to in by its associated edge . Hence, the number of subtrees connected to in is given by . To form a unique spanning tree, each has to be attached to at least one node of a subgraph obtained from extracting a node by connecting a root of each to any node , where denotes a set of node of the subgraph . Hence, there are unique tree topologies that can be obtained from each Prufer sequence since there are possible ways to attach all subtrees to .
The
Download
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
Bad Blood by John Carreyrou(6271)
Rich Dad Poor Dad by Robert T. Kiyosaki(6174)
Principles: Life and Work by Ray Dalio(5955)
Playing to Win_ How Strategy Really Works by A.G. Lafley & Roger L. Martin(5488)
Management Strategies for the Cloud Revolution: How Cloud Computing Is Transforming Business and Why You Can't Afford to Be Left Behind by Charles Babcock(4438)
The Confidence Code by Katty Kay(4033)
Thinking in Bets by Annie Duke(3995)
American Kingpin by Nick Bilton(3504)
Delivering Happiness by Tony Hsieh(3280)
Project Animal Farm: An Accidental Journey into the Secret World of Farming and the Truth About Our Food by Sonia Faruqi(3013)
The Power of Habit by Charles Duhigg(2962)
Mastering Bitcoin: Programming the Open Blockchain by Andreas M. Antonopoulos(2890)
Brotopia by Emily Chang(2889)
The Tyranny of Metrics by Jerry Z. Muller(2845)
I Live in the Future & Here's How It Works by Nick Bilton(2841)
The Marketing Plan Handbook: Develop Big-Picture Marketing Plans for Pennies on the Dollar by Robert W. Bly(2792)
The Content Trap by Bharat Anand(2776)
Building a StoryBrand by Donald Miller(2751)
Applied Empathy by Michael Ventura(2742)
