Minimum spanning tree on spatio-temporal networks

Viswanath Gunturi, Shashi Shekhar, Arnab Bhattacharya

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationDatabase and Expert Systems Applications - 21st International Conference, DEXA 2010, Proceedings
Pages149-158
Number of pages10
EditionPART 2
DOIs
StatePublished - 2010
Event21st International Conference on Database and Expert Systems Applications, DEXA 2010 - Bilbao, Spain
Duration: Aug 30 2010Sep 3 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume6262 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other21st International Conference on Database and Expert Systems Applications, DEXA 2010
CountrySpain
CityBilbao
Period8/30/109/3/10

Fingerprint Dive into the research topics of 'Minimum spanning tree on spatio-temporal networks'. Together they form a unique fingerprint.

Cite this