ГлавнаяАрхивО двух задачах аппроксимации взвешенных графов и алгоритмах их решения

О двух задачах аппроксимации взвешенных графов и алгоритмах их решения | Прикладная дискретная математика. 2013. № 3(21).

Рассматриваются две связанные задачи аппроксимации взвешенных графов. В качестве погрешности аппроксимации рассматривается абсолютная величина максимума разностей расстояний между вершинами исходного графа и соответствующими им вершинами графа аппроксимирующего. В первой задаче требуется минимизировать погрешность аппроксимации при заданной размерности аппроксимирующего графа. Во второй — минимизировать размерность аппроксимирующего графа при заданной погрешности. Для задач приводится постановка в терминах задачи разбиения графа, описываются эвристические алгоритмы решения и производится сравнение с решением известным алгоритмом разбиения графа.
  • Title О двух задачах аппроксимации взвешенных графов и алгоритмах их решения
  • Headline О двух задачах аппроксимации взвешенных графов и алгоритмах их решения
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(21)
  • Date:
  • DOI
Ключевые слова
аппроксимация графа, разбиение графа, уменьшение сложности задач, graph approximation, graph partitioning, sparse graphs, problem complexity reduction
Авторы
Ссылки
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.
О двух задачах аппроксимации взвешенных графов и алгоритмах их решения | Прикладная дискретная математика. 2013. № 3(21).
О двух задачах аппроксимации взвешенных графов и алгоритмах их решения | Прикладная дискретная математика. 2013. № 3(21).
Полнотекстовая версия