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.
Download file
Counter downloads: 71
- Title Two problems of weighted graphs approximation and their solution algorithms
- Headline Two problems of weighted graphs approximation and their solution algorithms
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(21)
- Date:
- DOI
Keywords
аппроксимация графа, разбиение графа, уменьшение сложности задач, graph approximation, graph partitioning, sparse graphs, problem complexity reductionAuthors
References
http://www.dis.uniroma1.it/challenge9/download.shtml — 9th DIMACS Implementation Challenge — Shortest Paths (дата обращения: май 2013).
Ураков А. Р., Тимеряев Т. В. Алгоритмы быстрого поиска для двух задач о метрических характеристиках взвешенных графов // Управление большими системами. 2013. Вып. 42. С. 153-172.
Andreev K. and Racke H. Balanced graph partitioning // Proc. sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. Barcelona, 2004. P. 120-124.
Kernighan B. and Lin S. An efficient heuristic procedure for partitioning graphs // The Bell System Techn. J. 1970. V.40(1). P. 291-307.
Hagen L. and Kahng A. New spectral methods for ratio cut partitioning and clustering // IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems. 1992. V. 11(9). P. 10741085.
Ильев В. П., Ильева С. Д. и др. Приближенные алгоритмы для задач аппроксимации графов // Дискретный анализ и исследование операций. 2007. Т. 18(1). С. 41-60.
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. P. 241-252.
KuhnF., Moscibroda T., et al. Unit disk graph approximation // Proc. Joint Workshop on Foundations of Mobile Computing. Philadelphia, 2004. P. 17-23.
Long B., Xiaoyun X., et al. Community learning by graph approximation // Proc. Seventh IEEE Intern. Conf. on Data Mining. Omaha, 2007. P. 232-241.
Jacob J., Jentsch M., et al. Detecting hierarchical structure in molecular characteristics of disease using transitive approximations of directed graphs // Bioinformatics. 2008. V. 24(7). P. 995-1001.
Koutis I., Levin A., et al. Improved spectral sparsification and numerical algorithms for SDD matrices // Proc. STACS. Paris, 2012. P. 266-277.
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. P. 13-18.
Fiduccia C. and Mattheyses R. A linear time heuristic for improving network partitions // DAC'82. Proc. 19th Design Automation Conf. Las Vegas, 1982. P. 175-181.
Ураков А. Р., Тимеряев Т. В. Многоуровневый алгоритм разбиения графов по критерию средней длины // Информационные технологии. 2012. №4. С. 22-25.
Two problems of weighted graphs approximation and their solution algorithms | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 3(21).
Download full-text version
Download fileCounter downloads: 319