6533b823fe1ef96bd127e395

RESEARCH PRODUCT

Minimum node weight spanning trees searching algorithm for broadcast transmission in sensor networks

Zbigniew Lipinski

subject

Discrete mathematicsSpanning treeComputer sciencegraph theory010401 analytical chemistryDecision treeComplete graph020206 networking & telecommunications02 engineering and technologyDirected graphspanning trees01 natural sciences0104 chemical sciencessensor networksSearch algorithm0202 electrical engineering electronic engineering information engineeringGraph (abstract data type)Algorithm designLaplacian matrixdata broadcasting

description

A minimum node weight spanning tree in a weighted, directed graph is a tree whose node with maximum out-weight is minimal among all spanning trees. This type of trees are important because they appear in the solutions of the maximum lifetime broadcasting problem in wireless sensor networks. In a complete graph build of N nodes there are NN-2 spanning trees and to find such trees it is necessary to perform more than O(NN-2) operations. In this paper we propose an algorithm for searching the minimum node weight spanning trees in the graph. In the proposed algorithm, instead of calculating the symbolic determinant of the generalized Laplacian matrix, numerical operations on its exponents are performed. This allows to reduce the best case complexity of the minimum node weight spanning trees searching problem to the complexity of calculating the determinant of a numeric N × N matrix.

yearjournalcountryeditionlanguage
2017-09-012017 Twelfth International Conference on Digital Information Management (ICDIM)
https://doi.org/10.1109/icdim.2017.8244691