Record Details

Efficient Spanning Tree Enumeration Using Loop Domain

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Efficient Spanning Tree Enumeration Using Loop Domain
 
Creator BHAGAT, NS
 
Subject network reconfiguration
graph
algorithm
algorithms
complexity theory
graph theory
tree searching
trees
 
Description Exhaustive enumeration of spanning trees in a graph requires substantial time and computational overheads. The proposed method, using the concept of LOOP DOMAIN, greatly reduces the complexity of enumeration. The initial graph is transformed into a graph in loop domain where the spanning tree enumeration is then carried out. Subsequently spanning trees of initial graph are generated. The proposed method eliminates all the two degree vertices in a graph. This finds application in power system distribution networks, which have substantial number of two degree vertices. The consequent reduction in size of graph and its corresponding trees is highly desirable. The proposed method is demonstrated on a 33 vertex system and reduction incomplexity is evaluated.
 
Publisher IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
 
Date 2011-08-01T02:05:03Z
2011-12-26T12:53:13Z
2011-12-27T05:40:28Z
2011-08-01T02:05:03Z
2011-12-26T12:53:13Z
2011-12-27T05:40:28Z
2009
 
Type Article
 
Identifier IEEE SYSTEMS JOURNAL, 3(4), 536-543
1932-8184
http://dx.doi.org/10.1109/JSYST.2009.2037287
http://dspace.library.iitb.ac.in/xmlui/handle/10054/8311
http://hdl.handle.net/10054/8311
 
Language en