TY - GEN

T1 - Minimum spanning tree on spatio-temporal networks

AU - Gunturi, Viswanath

AU - Shekhar, Shashi

AU - Bhattacharya, Arnab

PY - 2010

Y1 - 2010

N2 - Given a spatio-temporal network whose edge properties vary with time, a time-sub-interval minimum spanning tree (TSMST) is a collection of minimum spanning trees where each tree is associated with one or more time intervals; during these time intervals, the total cost of this spanning tree is the least among all spanning trees. The TSMST problem aims to identify a collection of distinct minimum spanning trees and their respective time-sub-intervals. This is an important problem in spatio-temporal application domains such as wireless sensor networks (e.g., energy-efficient routing). As the ranking of candidate spanning trees is non-stationary over a given time interval, computing TSMST is challenging. Existing methods such as dynamic graph algorithms and kinetic data structures assume separable edge weight functions. In contrast, we propose novel algorithms to find TSMST for large networks by accounting for both separable and non-separable piecewise linear edge weight functions. The algorithms are based on the ordering of edges in edge-order-intervals and intersection points of edge weight functions.

AB - Given a spatio-temporal network whose edge properties vary with time, a time-sub-interval minimum spanning tree (TSMST) is a collection of minimum spanning trees where each tree is associated with one or more time intervals; during these time intervals, the total cost of this spanning tree is the least among all spanning trees. The TSMST problem aims to identify a collection of distinct minimum spanning trees and their respective time-sub-intervals. This is an important problem in spatio-temporal application domains such as wireless sensor networks (e.g., energy-efficient routing). As the ranking of candidate spanning trees is non-stationary over a given time interval, computing TSMST is challenging. Existing methods such as dynamic graph algorithms and kinetic data structures assume separable edge weight functions. In contrast, we propose novel algorithms to find TSMST for large networks by accounting for both separable and non-separable piecewise linear edge weight functions. The algorithms are based on the ordering of edges in edge-order-intervals and intersection points of edge weight functions.

UR - http://www.scopus.com/inward/record.url?scp=78049385230&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78049385230&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15251-1_11

DO - 10.1007/978-3-642-15251-1_11

M3 - Conference contribution

AN - SCOPUS:78049385230

SN - 3642152503

SN - 9783642152504

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 149

EP - 158

BT - Database and Expert Systems Applications - 21st International Conference, DEXA 2010, Proceedings

T2 - 21st International Conference on Database and Expert Systems Applications, DEXA 2010

Y2 - 30 August 2010 through 3 September 2010

ER -