Geodesic
Two problems of weighted graphs approximation and their solution algorithms
Prikladnaâ diskretnaâ matematika, no. 3 (2013), pp. 86-92

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

Two approximation problems for weighted sparse graphs are considered. By the approximation error is meant the absolute value of the difference of the distances between the vertices in graph and the corresponding vertices in an approximation graph. The first problem is to minimize the approximation error under a given dimension of the approximation graph. The second problem is to minimize the dimension of the approximation graph under a given approximation error threshold. For both problems, their solution algorithms are proposed and their presentation in the form of a graph partitioning problem are presented.
Keywords: graph approximation, graph partitioning, sparse graphs, problem complexity reduction. 
@article{PDM_2013_3_a8,
     author = {A. R. Urakov and T. V. Timeryaev},
     title = {Two problems of weighted graphs approximation and their solution algorithms},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {86--92},
     publisher = {mathdoc},
     number = {3},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_3_a8/}
}
TY  - JOUR
AU  - A. R. Urakov
AU  - T. V. Timeryaev
TI  - Two problems of weighted graphs approximation and their solution algorithms
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 86
EP  - 92
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_3_a8/
LA  - ru
ID  - PDM_2013_3_a8
ER  - 
%0 Journal Article
%A A. R. Urakov
%A T. V. Timeryaev
%T Two problems of weighted graphs approximation and their solution algorithms
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 86-92
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_3_a8/
%G ru
%F PDM_2013_3_a8
A. R. Urakov; T. V. Timeryaev. Two problems of weighted graphs approximation and their solution algorithms. Prikladnaâ diskretnaâ matematika, no. 3 (2013), pp. 86-92. http://geodesic.mathdoc.fr/item/PDM_2013_3_a8/