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/

[1] Bonneau J., Anderson J., et al., “Eight friends are enough: social graph approximation via public listings”, Proc. Second ACM EuroSys Workshop on Social Network Systems, Nuremberg, 2009, 13–18 | DOI

[2] Koutis I., Levin A., et al., “Improved spectral sparsification and numerical algorithms for SDD matrices”, Proc. STACS, Paris, 2012, 266–277 | MR | Zbl

[3] Long B., Xiaoyun X., et al., “Community learning by graph approximation”, Proc. Seventh IEEE Intern. Conf. on Data Mining, Omaha, 2007, 232–241 | DOI

[4] Jacob J., Jentsch M., et al., “Detecting hierarchical structure in molecular characteristics of disease using transitive approximations of directed graphs”, Bioinformatics, 24:7 (2008), 995–1001 | DOI

[5] Kuhn F., Moscibroda T., et al., “Unit disk graph approximation”, Proc. Joint Workshop on Foundations of Mobile Computing, Philadelphia, 2004, 17–23

[6] Fertin G., Hermelin D., et al., “Common structured patterns in linear graphs: approximation and combinatorics”, Proc. 18th Annual Conf. on Combinatorial Pattern Matching, Berlin, 2007, 241–252 | DOI | MR | Zbl

[7] Ilev V. P., Ileva S. D. i dr., “Priblizhennye algoritmy dlya zadach approksimatsii grafov”, Diskretnyi analiz i issledovanie operatsii, 18:1 (2007), 41–60 | MR

[8] Kernighan B., Lin S., “An efficient heuristic procedure for partitioning graphs”, The Bell System Techn. J., 40:1 (1970), 291–307 | DOI

[9] Hagen L., Kahng A., “New spectral methods for ratio cut partitioning and clustering”, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 11:9 (1992), 1074–1085 | DOI

[10] Andreev K., Racke H., “Balanced graph partitioning”, Proc. sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, Barcelona, 2004, 120–124 | DOI

[11] Urakov A. R., Timeryaev T. V., “Algoritmy bystrogo poiska dlya dvukh zadach o metricheskikh kharakteristikakh vzveshennykh grafov”, Upravlenie bolshimi sistemami, 42, 2013, 153–172

[12] 9th DIMACS Implementation Challenge – Shortest Paths, , (data obrascheniya: mai 2013) http://www.dis.uniroma1.it/challenge9/download.shtml

[13] Fiduccia C., Mattheyses R., “A linear time heuristic for improving network partitions”, DAC' 82, Proc. 19th Design Automation Conf., Las Vegas, 1982, 175–181 | DOI

[14] Urakov A. R., Timeryaev T. V., “Mnogourovnevyi algoritm razbieniya grafov po kriteriyu srednei dliny”, Informatsionnye tekhnologii, 2012, no. 4, 22–25