Geodesic
Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph
Journal of the Belarusian State University. Mathematics and Informatics, Tome 2 (2017), pp. 37-43

Voir la notice de l'article provenant de la source Math-Net.Ru

The problem of locating sensors on the network to monitor flows has been object of growing interest in the past few years, due to its relevance in the field of traffic management and control. The basis for modeling the processes of estimating flows in generalized multinetwork is a sparse underdetermined system of linear algebraic equations of a special type. Sensors are located in the nodes of the multinetwork for the given traffic levels on arcs within range covered by the sensors, that would permit traffic on any unobserved flows on arcs to be exactly. The problem being addressed, which is referred to in the literature as the Sensor Location Problem (SLP), is known to be $NP$-complete. In this paper the effective algorithms are developed to determine the ranks of the matrices of each of the independent subsystems obtained as a result of applying the theory of decomposition. From the equality of the sum of the ranks of the matrices of independent subsystems and the number of unknowns in independent subsystems, the uniqueness conditions for the solution of a special sparse system of linear algebraic equations follow. The results of the research can also be applied to constructing optimal solutions to problems of mathematical programming.
Keywords: multigraph; sparse system; rank; decomposition; support; unique solution. 
L. Pilipchuk. Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph. Journal of the Belarusian State University. Mathematics and Informatics, Tome 2 (2017), pp. 37-43. http://geodesic.mathdoc.fr/item/BGUMI_2017_2_a5/
@article{BGUMI_2017_2_a5,
     author = {L. Pilipchuk},
     title = {Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {37--43},
     year = {2017},
     volume = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2017_2_a5/}
}
TY  - JOUR
AU  - L. Pilipchuk
TI  - Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2017
SP  - 37
EP  - 43
VL  - 2
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2017_2_a5/
LA  - ru
ID  - BGUMI_2017_2_a5
ER  - 
%0 Journal Article
%A L. Pilipchuk
%T Decomposition methods of sparse systems of linear algebraic equations for estimation of the traffic for the generalized multigraph
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2017
%P 37-43
%V 2
%U http://geodesic.mathdoc.fr/item/BGUMI_2017_2_a5/
%G ru
%F BGUMI_2017_2_a5

[1] L. Bianco, G. Confessore, M. Gentili, “Combinatorial aspects of the sensor location problem”, Ann. Oper. Res, 144 (2006), 201–234

[2] L. A. Pilipchuk, “Razrezhennye nedoopredelennye sistemy lineinykh algebraicheskikh uravnenii”, Minsk, 2012

[3] L. A. Pilipchuk, T. S. Vishnevetskaya, Y. H. Pesheva, “Sensor location problem for a multigraph”, Math. Balk. New Ser., 27 (2013), 65–75

[4] L. A. Pilipchuk, A. S. Pilipchuk, Y. V. Ramanouski, “Optimal location of sensors on a multigraph with zero split ratios of some arc flows”, AIP Conf. Proc., 1631 (2014), 350–353

[5] A. S. Pilipchuk, “Raspolozhenie minimalnogo chisla obozrevaemykh uzlov v obobschennom grafe dlya otsenki trafika ego nenablyudaemoi chasti”, Vestn. BGU. Fizika. Matematika. Informatika, 2015, 108–111

[6] L. A. Pilipchuk, A. S. Pilipchuk, “Sparse linear systems: theory of decomposition, methods, technology, applications and implementation in Wolfram Mathematica”, AIP Conf. Proc., 1690 (2015)

[7] L. A. Pilipchuk, O. V. German, A. S. Pilipchuk, “The general solutions of sparse systems with rectangular matrices in the problem of sensors optimal location in the nodes of a generalized graph”, Vestnik BGU. Fiz. Mat. Inform., 2015, 91–96