Network Optimization: An Introduction to the Network Reconstruction Approach

Network Reconstruction Approach to optimization

Elias Munapo, Santosh Kumar, Philimon Nyamugure, Trust Tawanda

• Publisher: River Publishers
• Year: 2025
• eBook ISBN: 9781040405123
• Edition: 0
• Topic: Computer Science
• Subtopic: Optimization
• Index: Computer Science

For every problem, mathematical or otherwise, there is more than one approach and much depends on the ingenuity of the person concerned. Consider that a person is interested in picking some fruit from a tree and is considering multiple picking options. One possibility is, if one can reach the fruit, just snip it to retrieve it. The second possibility is to alternatively apply force and detach the fruit from the tree. If neither option is possible, the fruit can still be detached from the tree, but how? A third possibility lies in the fact that just holding on to the fruit and turning it in one direction it can be picked. Similarly, many possibilities are seen by keen eyes while solving a mathematical problem. The reconstruction approach applied in this book is like the third possibility of holding a fruit and turning it in one direction until the desired solution is obtained.

This book is an introduction to reconstruction concepts and their applications for solving some network optimization problems. Networks are a mathematical abstraction of a given physical situation, which are described by using nodes, links (directed or non-directed) and link weights defining some associated properties of that physical system. Reconstruction ideas exploit the mathematical structure of a particular problem and find ways to reach the required solution. It is hoped that these ideas will be explored for other mathematical structures.

The authors have developed many methods to find optimal solutions for these network related problems and they observed that various methods discussed in 8 chapters have a common thread of reconstruction, which unites them, and that aspect motivated authors to develop this book.

Table of contents

• Cover Page
• Half Title Page
• Series Page
• Title Page
• Copyright Page
• Dedication
• Contents
• Preface
• Acknowledgement
• List of Figures
• List of Tables
• List of Abbreviations
• 1 Network Reconstruction – Unification of Assignment and Transportation Models and Accelerating the Search
• 2 Reconstruction Approach for the Shortest and Kth Shortest Routes in Networks
• 3 Network Reconstruction Approach to a Minimum Spanning Tree under an Index Restriction
• 4 Path through ‘k’ Specified Nodes or k’ Specified Links in Networks: A Reconstruction Approach
• 5 Is Determination of the Travelling Salesman Tour an NP Hard Problem? Some Polynomial Time Reconstruction Approaches
• 6 TANYAKUMU Labelling Method: Exact Algorithm for the Travelling Salesman Problem (TSP) and the Equality Generalized Travelling Salesman Problem (E-GTSP)
• 7 Some Reliability Routing Problems and Their Evaluation by Network Reconstruction
• 8 Reconstruction Approach to Reliability and Maximum Flows in Networks
• Index
• About the Authors