Minimum Loss Spanning Tree by Enumeration Using Loop Domain
by
Nitin Bhagat
Indian Institute of Technology Bombay

With loss for a tree given by monomial in flow over its branches , the search for MINIMUM LOSS SPANNING TREE (MLST) leads to NP Complete problem & hence necessarily involves exhaustive search techniques. Identification of global minima as well as use of multi-criteria objective function involves Spanning Tree Enumeration having a large number of distinct layouts. However enlisting all distinct layouts

without repetition requires substantial time & computational resources as well as use of complicated data structures. Real life electrical distribution networks have relatively large number of nodes & spanning tree layouts but have a small number of loops. Proposed LOOP DOMAIN graph has relatively less nodes & few spanning trees. Spanning tree enumeration is solved for loop domain graph. One to many mapping of spanning tree

is used to transform solution from loop domain to original graph. Neighborhood & Local Minima is defined for a spanning tree in loop domain. Proposed concept can be extended to enumeration of k forest, k cycles, cutset and special subgraphs, either containing or excluding some edges. Three examples, one from published literature and two real life

Date received: March 18, 2008