Connecting Supply and Demand Vertices with Fault Tolerance
Wenli Wang, Chris S. Coulston, Robert S. Weissbach, Mei-Huei Tang · International Journal of Computer Science Engineering and Applications · 2013
Fault tolerance can improve reliability and robustness when providing connectivity among entities.Many studies had accounted for entities that were uniform and similar in nature.However, applications today often require the entities to have distinguished roles.For instance, a power system has two types of entities: sources and loads.A source mainly concerns no disconnection from the network, while a load further favors connections to multiple sources to gain dependable services.Such non-uniformity in the requirements calls for a new fault tolerance modeling approach.This paper introduces a 2-edge supply/demand (2-ESD) connected problem.It is NP-hard like many connectivity problems.Algorithms are developed to satisfy different fault tolerance requirements of the entities.Edge reduction and refactoring are further employed to identify a better cost effective solution.Experiments were conducted to compare the cost of the derived 2-ESD network with that of the minimum spanning tree (MST) solution.