Методы и алгоритмы управления маршрутизацией в транспортных сетях на основе оперативной обработки информации в разреженных графах тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Тимеряев, Тимофей Валерьевич

• Тимеряев, Тимофей Валерьевич
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Тимеряев, Тимофей Валерьевич

СОДЕРЖАНИЕ

Введение

Глава 1. Анализ современного состояния в области оперативного управления маршрутизацией транспортных средств

1.1. Техническая постановка задачи оптимизации оперативных транспортных перевозок

1.2. Обзор задач поиска оптимальных путей в транспортных сетях и алгоритмов их решения

1.3. Обзор задач уменьшения размерности графа транспортной сети

Выводы по 1-й главе

Глава 2. Задача поиска оптимальных путей между всеми парами узлов транспортной сети

2.1. Алгоритм разборки-сборки графа транспортной сети

2.2. Доказательство получения точного оптимального решения с помощью алгоритма разборки-сборки графа транспортной сети

2.3. Примеры решения задачи поиска оптимальных путей с помощью

алгоритма разборки-сборки графа транспортной сети

Выводы по 2-й главе

Глава 3. Поиск метрических характеристик и уменьшение размерности графа транспортной сети

3.1. Задача поиска метрических характеристик транспортной сети

3.2. Метод и алгоритм поиска центра и радиуса транспортной сети

3.3. Метод и алгоритм поиска диаметра транспортной сети

3.4. Уменьшение размерности графа транспортной сети

Выводы по 3-й главе

Глава 4. Программная реализация разработанных алгоритмов и анализ

полученных результатов

4.1. Данные и методика тестирования

4.2. Поиск оптимальных путей между всеми парами узлов транспортной сети

4.3. Поиск метрических характеристик транспортной сети

4.4. Уменьшение размерности графа транспортной сети

4.5. Внедрение разработанного программного обеспечения

Выводы по 4-й главе

Заключение

Список литературы

Приложение 1. Среднее время решения задач уменьшения размерности

графа транспортной сети разными алгоритмами

Приложение 2. Акт о внедрении

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы управления маршрутизацией в транспортных сетях на основе оперативной обработки информации в разреженных графах»

ВВЕДЕНИЕ

Актуальность темы исследования

Транспорт — одна из основных отраслей материального производства. На транспорте, как в добывающей и обрабатывающей промышленности и в сельском хозяйстве, создается стоимость. Однако транспорт имеет ряд своеобразных черт. Его продукция — изменение местоположения, перемещение грузов и людей. Эта продукция создается и потребляется одновременно, в самом процессе работы транспорта [36].

Многие современные области промышленности в различном объеме содержат транспортную систему (ТС). В зависимости от типа предприятия ТС может представлять собой: локальную транспортную сеть предприятия, дорожную сеть территориального образования, в пределах которого расположены цеха/филиалы предприятия, совокупность авиалиний между пунктами производства и доставки т.д. В тех случаях, когда ТС имеет значительное влияние на характер работы промышленного предприятия, некоторыми из способов повышения эффективности работы предприятия и сокращения издержек являются оперативный мониторинг и оптимизация процессов связанных с ТС.

Как правило, ТС моделируется нагруженными графовыми структурами. При этом для многих из решаемых на практике графовых задач известные алгоритмы имеют полиномиальную по входным параметрам сложность. Ряд часто возникающих на нагруженных графах задач транспортного характера относится к ]ЧР-трудным. С целью получения их решения за приемлемое время используются эвристические методы, не дающие оптимального решения.

События последних десятилетий в транспортной промышленности связаны со становлением и бурным развитием ее компьютеризации. Сопутствующее массовое распространение навигационных систем на основе цифровой картографии привело к появлению большого числа картографических сервисов (как коммерческих, так и бесплатных) с большим объемом накопленных данных и различными интерфейсами доступа к ним. Таким образом, при решении

прикладных задач с ТС стало возможным использование карт с высокой степенью точности и актуальности.

Очень актуальной в настоящее время является задача поддержки принятия решений при управлении маршрутизацией транспортных средств, занимающихся перевозкой. Заявки на перевозку поступают в систему управления в режиме реального времени. Требуется оптимизировать работу системы диспетчеризации транспортных средств с целью минимизации по одному из возможных критериев: суммарный пробег транспортных средств, максимальное и среднее время транспортировки грузов и т.д. На решение задачи оказывает влияние динамический характер транспортной сети, на которой осуществляется диспетчеризация транспортных средств. При распределении поступающих заявок между транспортными средствами учитываются изменения конфигурации транспортной сети, обусловленные возникающими аварийными ситуациями, пробками, дорожными работами, природными и другими факторами.

Применение цифровой картографической информации для моделирования транспортной сети крупных территориальных образований при решении задачи диспетчеризации транспортных средств связно с медленным откликом системы диспетчеризации ввиду высокой сложности решения проблемы, зависящей от размерности транспортной сети. Поэтому повышение эффективности решения проблемы управления назначениями заданий транспортных средств на сетях большой размерности за счет декомпозиции исходной графовой структуры является актуальным.

Степень разработанности темы Задачами оптимизации транспортных сетей и разработки алгоритмов поиска кратчайших путей занимались А. О. Алексеев, С. И. Сергеев, И. И. Меламед, Ю.И. Палагин, Т.И. Михеева, У. Цвик, М.Торуп, A.B. Голдберг, Х.Н. Габов.

Методы поиска метрических характеристик графов изложены в работах отечественных и зарубежных ученных A.M. Раппопорта, Р. Юстера, П. Крешензи, Ф.В. Тейкса, Ф.Ф. Драгана.

Задачам аппроксимации графов в различной постановке посвящены работы российских ученных В.П. Ильева, A.A. Агеева, Г.Ш. Фридмана, а также зарубежных ученных П. Сандерса, Д. Шпилмана, Д. Добкина, Дж. Лесковеца, Дж. Капириса.

Объект исследования: транспортные сети большой размерности пред ставимые в виде графовых структур высокой степени точности.

Предмет исследования: методы и алгоритмы оптимизации работы транспортных сетей на основе системного анализа нагруженных графовых структур большой размерности.

Целью работы является повышение эффективности работы транспортных сетей большой размерности путем поддержки принятия решений в системе оперативного управления маршрутизацией транспортных средств на основе декомпозиции графовых структур. Задачи исследования:

1. Разработать алгоритм эффективного поиска оптимальных путей на основе оперативной обработки информации в транспортных сетях большой размерности.

2. Разработать метод и алгоритмы эффективного определения метрических характеристик транспортных сетей.

3. Разработать метод и алгоритмы понижения размерности нагруженных графов, моделирующих транспортные сети, для получения возможности управления транспортными средствами в реальном масштабе времени.

4. Разработать программное обеспечение для решения задачи понижения размерности разреженных нагруженных графов, моделирующих транспортные сети, на базе разработанных алгоритмов. Провести анализ эффективности разработанных алгоритмов и программного обеспечения.

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения.

В главе 1 приведен аналитический обзор задач и алгоритмов поиска кратчайших путей в нагруженных графах и их метрических характеристик (радиуса, центра и диаметра). Рассмотрены некоторые технические задачи,

сводимые к решению с помощью графов. Проведен анализ существующих методов и их недостатков для решения задач поиска кратчайших путей и аппроксимации графов. Выделены известные эффективные и широко применяемые способы решения этих задач. Поставлены цель и задачи исследования.

В главе 2 приводится постановка и описание алгоритма «разборки-сборки графа» (р. 2.1) для решения задачи поиска кратчайших путей между всеми вершинами. Описаны этапы разборки (декомпозиции) и сборки графа. В результате сборки графа находится матрица кратчайших расстояний и матрица последователей, по которой можно восстановить кратчайший путь между любыми двумя вершинами исходного графа.

В р. 2.2 дано обоснование получения точного решения задачи поиска минимальных путей разработанным алгоритмом. В р. 2.3 разобраны примеры применения разработанного алгоритма.

В главе 3 разработаны алгоритмы поиска метрических характеристик графа (радиуса, центра, диаметра) (р. 3.1), а также разобраны примеры применения разработанных алгоритмов. В р. 3.2 на основе алгоритмов из р. 3.1 решается задача аппроксимации нагруженного графа большой размерности графом меньшей размерности с целью минимизации разностей расстояний между вершинами исходного графа и соответствующими им вершинами полученного малого графа. Разобран пример решения задачи аппроксимации неориентированного нагруженного графа.

В главе 4 проведены вычислительные эксперименты для оценки эффективности разработанных алгоритмов поиска кратчайших путей, нахождения метрических характеристик и аппроксимации графов. В качестве тестовых данных используется несколько наборов графов. Графы дорожных сетей крупнейших городов России и других стран из картографического проекта Ореп81хеегМар.

В приложении приведено среднее время решения второй задачи аппроксимации разными алгоритмами.

Результаты, выносимые на защиту:

1. Алгоритм эффективного поиска оптимальных путей на основе оперативной обработки информации в транспортных сетях большой размерности.

2. Метод и алгоритмы эффективного определения метрических характеристик транспортных сетей.

3. Метод и алгоритмы понижения размерности нагруженных графов, моделирующих транспортные сети, для получения возможности управления транспортными средствами в реальном масштабе времени.

4. Программное обеспечение для решения задачи понижения размерности разреженных нагруженных графов, моделирующих транспортные сети, результаты анализа эффективности разработанных алгоритмов и программ, проведенного с помощью вычислительного эксперимента.

Научная новизна полученных результатов заключается в следующем:

1. Разработан алгоритм поиска оптимальных путей в транспортных сетях большой размерности, включающий декомпозицию нагруженного графа, который отличается от известных тем, что на заключительном этапе алгоритма применяется композиция графа, что позволяет осуществлять принятие решений в системе оперативного управления маршрутизацией транспортных средств.

2. Предложен метод определения метрических характеристик транспортной сети, основанный на использовании множества опорных вершин, на основе метода разработаны алгоритмы определения радиуса и диаметра транспортной сети, отличающиеся от известных тем, что не требуют получения матрицы оптимальных расстояний, что позволяет декомпозировать нагруженный граф, моделирующий транспортную сеть, с заданной погрешностью.

3. Предложены метод и алгоритмы понижения размерности нагруженных графов, моделирующих транспортные сети, отличающиеся от известных тем, что исходному графу ставится в соответствие граф с меньшим числом вершин и минимизируется погрешность определения расстояний, что позволяет решать задачи маршрутизации транспорта в реальном масштабе времени.

Методы исследования

Результаты исследований, выполненных в работе, основаны на базовых положениях системного анализа, исследования операций и обработки исходной информации. В процессе исследований использовались вычислительные эксперименты для оценки эффективности разработанных алгоритмов. Достоверность результатов

Обоснованность результатов, полученных в диссертационной работе, базируется на использовании апробированных научных положений, методов исследования, корректном применении математического аппарата, согласовании новых научных результатов с известными теоретическими положениями. Достоверность теоретических положений и выводов подтверждается результатами апробации разработанных алгоритмов с помощью вычислительного эксперимента на большом объеме исходных данных, представляющих собой графовые модели дорожных сетей России и других стран.

Теоретическая и практическая значимость

Предложенные метод и алгоритмы аппроксимации сетевых графов позволяют решать задачи маршрутизации транспортных средств, а также проводить системный анализ и мониторинг работы в транспортных системах большой размерности в масштабе реального времени, что ранее было не доступно в динамически изменяемых окружениях.

Разработанное программное обеспечение для решения задачи понижения размерности разреженных нагруженных графов, моделирующих транспортные сети, позволяет сократить общую стоимость транспортных перевозок при оперативном управлении маршрутизацией транспортных средств в среднем на 15% по сравнению с известными методами.

Результаты работы внедрены в ООО «Эксперт» (г. Уфа), что подтверждается актом о внедрении. Публикации

Основные результаты диссертации отражены в 17 научных трудах, в том числе в 8 статьях в изданиях, рекомендованных ВАК, 9 - в других изданиях.

Основные материалы диссертации опубликованы в работах автора [15-25], и в соавторстве [5, 27-35, 230]. В работах [5, 27-35, 230] диссертанту принадлежат разделы, касающиеся разработки и усовершенствования методов и алгоритмов поиска кратчайших путей, метрических характеристик и аппроксимации графов, а также проведение вычислительного эксперимента и анализ его результатов. Апробация работы

По основным результатам работы были сделаны доклады на конференциях: Всероссийская зимняя школа-семинар аспирантов и молодых ученых «Актуальные проблемы науки и техники» (Уфа, 2010, 2012, 2014); XXXVI Международная молодежная научная конференция «Гагаринские чтения» (Москва, 2010); Всероссийская научная конференция молодых ученых «Наука. Технологии. Инновации» (Новосибирск, 2010); V Всероссийская конференция «Проблемы оптимизации и экономические приложения» (Омск, 2012); Всероссийская молодежная научная конференция «Мавлютовские чтения» (Уфа, 2009, 2011, 2012); Вторая международная научная конференция «Информационные технологии и системы» (Челябинск, 2013); Международная конференция «Информационные технологии интеллектуальной поддержки принятия решений». Российско-немецкий семинар «Модели и алгоритмы прикладной оптимизации» (Уфа, 2013), Всероссийская научно-практическая конференция "Механика: современное состояние, проблемы, перспективы" (Чебоксары, 2014), а также на научных семинарах кафедры высокопроизводительных вычислительных технологий и систем Уфимского государственного авиационного технического университета.

Глава 1. Анализ современного состояния в области оперативного управления маршрутизацией транспортных средств

1.1. Техническая постановка задачи оптимизации оперативных транспортных перевозок

Анализ факторов отрасли транспортных перевозок показывает, в частности, что грузооборот автомобильного транспорта с 2000 года увеличился на 60% (рис. 1.1). При этом рост пассажирооборота за тот же период времени составил 10%, особенно динамично этот рост происходил в последние 5 лет (рис. 1.2).

Рис. 1.1. Динамика грузооборота автомобильного транспорта в России,

2000-2013 гг

По ряду экономических причин в последнее время увеличивается значимость одной из разновидностей транспортных перевозок - оперативных перевозок. Особенность оперативных перевозок заключается в срочности заказов - необходимости выполнения большей части перевозок за ограниченный (часами, минутами) промежуток времени с момента их поступления. Основными потребителями оперативных перевозок являются малые предприятия и частные лица, а предоставляются они чаще всего частными коммерческими предприятиями. К специфике отрасли оперативных перевозок можно также

отнести: возможность корректировки/отмены заказов, круглосуточность перевозок, неравномерность потока заказов, высокую конкуренцию.

Пассажирооборот транспорта общего пользования

550 540 530

2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013

Год

Рис. 1.2. Динамика пассажирооборота транспорта общего пользования в

России, 2000-2013 гг

Наиболее важными факторами роста отрасли оперативных транспортных перевозок являются:

1) рост размеров населенных пунктов;

2) неэффективность работы государственных перевозчиков;

3) увеличение динамичности жизни граждан;

4) рост благосостояния населения.

Организацией оперативных перевозок занимаются автотранспортные предприятия (АТП). Типовая организационная структура АТП представлена на рис. 1.3.

Основной задачей АТП в рыночных условиях является увеличение прибыли за счет повышения качества предоставляемых услуг. Это достигается за счет уменьшения времени выполнения поступающих заявок, снижения расходов, связанных с перевозкой.

Генеральный директор

г

т

т

Отдел Главный Главный кадров 11 бухгалтер экономист

Бухгалтерия

Планово-экономический отдел

I

Заместитель директора по эксплуатации

........

Диспетчерская служба

Главный инженер

Ремонтная служба 1 Отдел снабжения Администра-тавно-хозяйст-венный отдел

-у-

Экономическая служба

J

Повышение экономической эффективности предприятия Финансовый мониторинг и отчетность ■ Повышение эффективности эксплуатационной деятельности

"V"

J

Эксплуатационная служба

• Организация перевозок в соответствии с разработанным планом

• Инструктаж и контроль движения водителей

• Контроль движения транспортных средств

отношения линейного руководства отношения функционального руководства

-V-

Техническая служба

J

• Хранение и выпуск на линию транспортных средств

• Планирование и организация тех. обслуживания

• Учет, хранение и выдача ГСМ и

запчастей

• Укрепление производственно-технической части

Рис. 1.3. Организационная структура АТП

Таким образом, актуальной задачей является совершенствование и оптимизация управления транспортными потоками (оперативного управления маршрутизацией транспортных средств).

Информация о выполнении заданий, местоположении и состоянии дорог

Рис. 1.4. Структура системы оперативного управления маршрутизацией

транспортных средств

Анализ функционирования различных АТП позволяет выделить наиболее важные элементы организационной структур, найти общие элементы и различия условий работы АТП (рис. 1.4). Управляющее звено представляет собой группу диспетчеров, в обязанности которых входит прием заявок (с использованием современных средств телекоммуникаций), размещение заявок в системе поддержки принятия решений (СППР), получение рекомендаций от СППР и назначение конкретного транспортного средства на выполнения поступившей заявки.

Рис. 1.5. Структура системы поддержки принятия решений при управлении маршрутизацией транспортных средств

Структура СППР содержит, в частности, следующие элементы (рис. 1.5):

1) модуль обработки информации (интерфейс) в который поступает информация о заказах и транспортных средствах;

2) модуль решения задачи маршрутизации транспорта;

3) базу данных оптимальных расстояний между узлами сети населенного пункта.

Методом оптимизации перевозок в данном случае является решение задачи маршрутизации транспорта, которая заключается в следующем.

Имеется транспортная сеть (рис. 1.6), состоящая из узлов погрузки и доставки, парк транспортных средств, находящихся в различных узлах сети. Известны цена и время перевозки между узлами сети в текущий момент времени. В режиме реального времени поступают заявки на перевозку из одного узла сети в другой.

Необходимо найти оптимальный план перевозок, включающий назначение конкретного транспортного средства на выполнение конкретной заявки.

Рис. 1.6. Пример транспортной сети. Темным цветом выделены узлы погрузки,

При решении задачи маршрутизации необходимо учитывать различные ограничения:

1) грузоподъемность (вместимость) транспортных средств;

2) срочность или необходимость доставки к определенному времени;

3) последовательность выполнения заявок одним транспортным средством;

4) наличие пробок и дорожных работ на участках сети.

Таким образом, задача маршрутизации является слишком вычислительно сложной для оперативного управления на реальных транспортных сетях крупных населенных пунктов, насчитывающих 104-106 узлов.

Для оптимизации оперативных транспортных перевозок в диссертационной работе предлагается решить задачу декомпозиции транспортной сети путем аппроксимации графа транспортной сети графом меньшей размерности с минимизацией погрешности, возникающей за счет огрубления графа.

штрихом - узлы доставки

В связи с этим в схему СППР вводятся модули понижения размерности графа транспортной сети и определения (пересчета) минимальных расстояний (рис. 1.5). Команда на запуск этих модулей выдается лицом, принимающим решения (начальником диспетчерского отдела). Основные определения

Рассматривается задача APSP (allpairs shortest path problem) для нагруженных ориентированных и неориентированных разреженных графов большой размерности с неотрицательными весами ребер (для простоты дуги ориентированного графа также будем называть ребрами).

Нагруженным неориентированным графом G = (V,E,U) называется тройка множеств:

- V = (v!,v2,...,vn) - множество вершин, будем считать число вершин |F| = п;

- £сК х F - множество ребер графа {v,-, Vj} = e(i, j), будем считать, что количество ребер \Е\ - т;

- U: » [0,+оо) - весовая функция на ребрах, вес ребра между вершинами и Vj обозначим u(v;,vj), для вершин v{ и Vj, не связанных ребром, полагается

u(Vi,Vj) = со.

Нагруженный граф задается матрицей длин ребер (дуг). Вершины , Vj называются смежными, если jv,-, vy} е Е. Если вершины Vj,Vj еК и e(i,j)GE, то ребро e(i,j) инцидентно вершинам vf и vj .

Степень d(vf) вершины v{ - количество ребер (дуг) графа, инцидентных v,-.

Граф называется разреженным, если справедливо т«п2. Граф называется полным, если любая пара вершин соединена одним ребром.

Путь в графе - чередующаяся последовательность вершин и ребер Пч).<-* = 'v/* )= % v.v^ ,e{ik^,ik),vik , каждое ребро

инцидентно двум вершинам - непосредственно предшествующей ему и непосредственно следующей за ним.

Длина пути - сумма весов входящих в путь ребер.

Кратчайший путь П(уг-,уу) между вершинами у, и Vj - путь между V,- и

Vj минимальной длины.

Расстояние га(уг-,уу) между у, и vJ■ - длина кратчайшего пути между VI и

Vj (/я(У/,У/) = 0,1 = 1,...,И).

Матрица минимальных расстояний графа - матрица М размерности пхп с элементами т(уг-, ).

Граф связный, если между любыми двумя его вершинами существует путь, то есть т(уг-,уу) < оо для всех г,у.

Простые графы - без петель и кратных ребер.

Между двумя вершинами графа может существовать несколько кратчайших путей. Это обстоятельство в данной работе не является существенным, поэтому при всех упоминаниях кратчайшего пути будем подразумевать любой кратчайший путь.

Пусть п(уг,уу) - кратчайший путь в графе С. Тогда любой его подпуть

тоже является кратчайшим.

Матрица последователей - матрица Р размерности пхп, элемент /?(уг-,уу)

которой представляет собой идентификатор вершины, которая следует за вершиной у,- в кратчайшем пути от Уг- и . Т.е. элементы матрицы Р

определяются по формуле

уь если е(|Д)еПх(у;,у ), = < ] (1.1)

[0 в ином случае.

С использованием матрицы Р кратчайший путь П5(уг,уу) для вершин vi Ф Vj в связном графе может быть определен по рекуррентной формуле

n'(v„v,)=<

v/{v/,jp(vi,vy)}ni(p(v/,vy),vy) p{yhVj)*Vj, i \ (1-2)

Поскольку подпуть n5(p(v;-, Vy),Vy) является кратчайшим, то

последователем вершины p(Vj,Vj) является вершина p{p(Vj,Vj),Vj). Таким

образом, решение задачи определения кратчайших путей действительно сводится к нахождению матрицы Р, т.е. можно утверждать, что кратчайший путь, связывающий любую пару вершин v,-,Vy, можно восстановить с помощью

матрицы последователей.

Метрическими характеристиками связного графа называют пару определяемых через расстояния в графе числовых характеристик - радиус и диаметр - и два связных с этими числами множества вершин - центр и периферийные вершины.

Эксцентриситет f(v,) вершины V,- - максимальное из всех кратчайших расстояний от уг- до всех остальных вершин s(v;)= max (w(yz-,vy)).

j=\,...,n

Диаметр графа - максимальное из всех кратчайших расстояний между

вершинами графа d - max (т(уг-,Уу])= max f(v; ).

i,j=\,...,n i=\,...,n

Вершины V/, эксцентриситет которых равен диаметру графа s{yi) = d, называют периферийными, D- {vz-1 s(vi) = d}. Периферийные вершины находятся на расстоянии диаметра друг от друга.

Центры графа - вершины, эксцентриситеты которых минимальны. Радиус графа - минимальный эксцентриситет г = min (¿•(v/-)).

Задачей о кратчайших путях с единственным источником (Single Source Shortest Paths, SSSP) называется задача, в которой задан граф G=(V,E), и необходимо найти кратчайшие пути от заданной вершины v,- до всех остальных Vj g V. Поиск кратчайших расстояний от вершины v{ до всех остальных будем обозначать SSSP(v,-).

1.2. Обзор задач поиска оптимальных путей в транспортных сетях и алгоритмов их решения

Классическая задача о кратчайшем пути (shortest path problem, SP) [243] в наиболее общем виде формулируется как «найти пути между элементами двух множеств вершин V^V2 графа так, чтобы длины найденных путей являлись минимальными в данном графе между соответствующими вершинами».

Задача о кратчайшем пути является одной из важнейших в алгоритмической теории графов. Существуют различные формулировки задачи, отличающиеся разнообразными сочетаниями мощностей множеств вершин графа, между которыми требуется найти кратчайшие пути, возможностью динамического изменения весов ребер графа. Классификацию задач можно также производить по наложенным дополнительным ограничениям. Другими разновидностями задачи являются: поиск почти кратчайших путей (almost shortest path), когда требуется найти путь между вершинами, не превышающий кратчайший на некоторую величину в и задача к кратчайших путей, в которой ищется к различных кратчайших путей между данными вершинами.

Различный выбор множеств вершин Vi,V2, между которыми ищутся пути, порождает различные постановки задачи. В табл. 1.1 приведена классификация классических задач о кратчайшем пути, основанная на различии мощностей множеств V\,V2.

Для неориентированных графов задачи пар (SSSP, SDSP), (SSMDSP, MSSDSP) и (MSSP, MDSP) являются эквивалентными. Для ориентированных графов задачи SDSP, MSSDSP и MDSP сводятся, соответственно, к задачам SSSP, SSMDSP и MSSP сменой направления у всех дуг графа. В таблице задачи (за исключением MPSP, сложность поиска решения которой зависит от мощностей множеств Vx и V2) расположены по не убыванию сложности. Решение каждой из более сложных задач позволяет получить решение для каждой из менее сложных, но с дополнительными вычислительными затратами.

В постановке задачи о динамическом кратчайшем пути (задачи о кратчайшем пути в динамическом графе, dynamic shortest path, DSP) [188] учитывается возможность получения информации о кратчайших путях графа, связь между вершинами и веса ребер которого изменяются во времени.

Таблица 1.1. Классификация задач о кратчайшем пути (8Р) по мощностям множеств У\, У2

Название Множество Ух Множество У2 Поиск путей

О кратчайшем пути между заданной парой вершин (single-pair shortest path, SPSP) Одна вершина У5 Одна вершина Из в V,

Список литературы диссертационного исследования кандидат наук Тимеряев, Тимофей Валерьевич, 2015 год

Литература

1. Алексеева E.B. Алгоритмы локального поиска для задачи о р-медиане с предпочтениями клиентов: дис. ... канд. физ.-мат. наук: 01.01.09 / Алексеева Екатерина Вячеславовна. - Новосибирск, 2007. - 92 с.

2. Васильев И.Л. Метод декомпозиции для задачи о р-медиане на несвязном графе // Дискрета, анализ и исслед. опер., сер. 2. 2007. Том 14, №1. С. 43-58.

3. Евстигнеев В.А. Применение теории графов в программировании. М: Наука, 1985.352 с.

4. Есиков О.В., Изотов Д.В. Задача выбора числа и мест размещения центров хранения и обработки информации в компьютерной сети // Бизнес-информатика. 2011. №4(18). С. 62-67.

5. Житников В.П., Ураков А.Р., Тимеряев Т.В. Оценка достоверности и аппроксимация информации, представленной взвешенным графом // Вестник УГАТУ, 2013. Т. 17, №2 (55). С. 50-52.

6. Зарецкий К.А. Построение дерева по набору расстояний между висячими вершинами // Успехи математических наук. 1965. Том 20, № 6(126). С. 94-96.

7. Ильев В.П., Ильева С.Д. и др. Приближенные алгоритмы для задач аппроксимации графов // Дискретный анализ и исследование операций. Т. 18, №1. 2011. С. 41-60.

8. Ильев В.П., Навроцкая A.A. Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера // Прикладная дискретная математика. 2011. №3. С. 80-84.

9. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. - СПБ.: БХВ - Петербург, 2003. 1104 с.

10. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.

11. Навроцкая A.A. Задачи аппроксимации графов и наследственных систем: дис. ... канд. физ.-мат. наук: 01.01.09 / Навроцкая Анна Александровна. - Омск, 2012. -90 с.

12. Смоленский Е.А. Об одном способе линейной записи графов / Журнал вычислительной математики и математической физики. № 2(2). С. 371-372.

13. Татаринов Е.А. Восстановление графа коллективом автоматов // Прикладная дискретная математика. Приложение. 2012. №5. С. 97-98.

14. Татаринов Е.А..Базовый алгоритм восстановления конечного графа // Труды ИПММ НАН Украины. 2010. Т 21. С. 216-227.

15. Тимеряев Т. В. Алгоритмы быстрого поиска центра, радиуса и диаметра взвешенного графа // Сб. ст. седьмой Всероссийск. зимн. шк.-семинара аспирантов и молодых ученых «Актуальные проблемы науки и техники», 14-16 февраля 2012. Информационные и инфокоммуникационные технологии. Т. 1. Уфа: УГАТУ, 2012. С. 296-298.

16. Тимеряев Т.В. Алгоритм разборки и сборки для поиска кратчайших путей графа // Сб. научн. тр. восьмой Всероссийск. зимн. шк.-семинара аспирантов и молодых ученых «Актуальные проблемы науки и техники», 19-20 февраля 2013. Управление в социально-экономических системах, естественные науки. Т. 3. Уфа: УГАТУ, 2013. С. 295-298.

17. Тимеряев Т.В. Аппроксимация взвешенного графа // Материалы всерос. научн. конф. молодых ученых «Наука. Технологии. Инновации» в 6-ти частях. Новосибирск: Изд-во НГТУ, 2011. Часть 1. С. 268-270.

18. Тимеряев Т.В. Быстрый поиск кратчайших путей разреженных графов // Тр. междунар. конф. «Информационные технологии интеллектуальной поддержки принятия решений». Российско-немецкий семинар «Модели и алгоритмы прикладной оптимизации» Т. 2. Уфа: УГАТУ, 2013. С. 201-203.

19. Тимеряев Т.В. Минимизация максимальной средней длины как критерий разбиения графа // Всерос. молодежи, научн. конф. «Мавлютовские чтения»: сб. тез. докл. Уфа: УГАТУ, 2011. Т.5. С. 76-78.

20. Тимеряев Т.В. Об особенностях одного типа взвешенных графов и их использовании для эффективного решения задач // Всерос. молодежи, научн. конф. «Мавлютовские чтения»: сб. трудов. Уфа: УГАТУ, 2012. Т.5 (4.1). С. 73-74.

21. Тимеряев Т.В., Шерыхалина Н.М. Оперативное определение оптимальных путей транспортных сетей (статья на англ. яз.) // Proceedings of 16-th Workshop on Computer Science and Information Technologies (CSIT'2014), Vol. 2., Sheffield, England, 2014. P. 102-106.

22. Тимеряев T.B., Шерыхалина Н.М. Определение оптимальных путей транспортной сети на базе графовой декомпозиции // Proceedings of the 2nd International Conférence "Intelligent Technologies for Information Processing and Management", Volume 2, November 10-12, Ufa, Russia, 2014. P. 71-75.

23. Тимеряев T.B. Оценка достоверности и аппроксимация информации, представленной взвешенным графом // Всерос. молодежи, научн. конф. «Мавлютовские чтения»: сб. тез. докл., Т.5. - Уфа: УГАТУ, 2009. - С. 39-40.

24. Тимеряев Т.В. Оценка достоверности и аппроксимация информации, представленной взвешенным графом // Сб. тр. 5-й Всероссийск. зимн. шк.-семинара аспирантов и молодых ученых, 17-20 февраля 2010. «Актуальные проблемы науки и техники». Уфа: УГАТУ, 2010. Т. 3. С. 283-286.

25. Тимеряев Т.В. Сбор информации и автоматизация построения графов для задач на макроуровне // XXXVI Гагаринские чтения: науч. тр. Междунар. молодежи, науч. конф. М.: МАТИ, 2010. Т. 5. С. 151-153.

26. Узденов А.А. Гарантированные оценки р-медиан на предфрактальном графе с затравкой - полный n-вершинный граф // XVII Международная научная конференция "Математические методы в технике и технологиях ММТТ-17, 2004. С. 180-181.

27. Ураков А. Р., Тимеряев Т.В. Использование особенностей взвешенных графов для более быстрого определения их характеристик // Прикладная дискретная математика. 2(16)/2012, Томск: ТГУ. С. 95-99.

28. Ураков А.Р., Михтанюк А.А., Тимеряев Т.В. Быстрый поиск характеристик взвешенного графа по матрице кратчайших расстояний // Вестник УГАТУ, 2012. Т. 15, №6 (51). С. 164-166.

29. Ураков А.Р., Тимеряев Т.В. Алгоритм поиска кратчайших путей для разреженных графов большой размерности // Прикладная дискретная математика. 1(19)/2013, Томск: ТГУ. С. 84-92.

30. Ураков А.Р., Тимеряев Т.В. Алгоритм поиска кратчайших путей разреженных графов большой размерности // Труды Второй междунар. науч. конф. «Информационные технологии и системы», Банное, Россия 27 февраля - 3 марта 2013 г. Челябинск: ЧелГУ, 2013. С. 108-110.

31. Ураков А.Р., Тимеряев Т.В. Алгоритмы быстрого поиска для двух задач о метрических характеристиках взвешенных графов // Управление большими системами. Вып. 42. 2013. С. 153-172.

32. Ураков А.Р., Тимеряев Т.В. Многоуровневый алгоритм разбиения графов по критерию средней длины / М.: Информационные технологии. 2012, №4. С. 22-25.

33. Ураков А.Р., Тимеряев Т.В. О двух задачах аппроксимации взвешенных графов и алгоритмах их решения // Прикладная дискретная математика. 3(21)/2013, Томск: ТГУ. С. 86-92.

34. Ураков А.Р., Тимеряев Т.В. Разбиение графа с минимизацией средних перемещений // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 5(133)/2011, СПб, 2011. - С. 96-99.

35. Ураков А.Р., Тимеряев Т.В. Точные алгоритмы быстрого поиска метрических характеристик графов дорожных сетей // Проблемы оптимизации и экономические приложения: материалы V Всероссийской конференции. Омск: Изд-во Ом.гос.ун-та, 2012. С. 214.

36. Ушаков С.С., Василевский Л.И. Транспортная система мира. М.: Транспорт, 1971. 216с.

37. Юшманов С.В. Восстановление графа по некоторому подмножеству столбцов его матрицы расстояний // Математические заметки. 1982. Том 31, № 4. С. 641651.

38. 9th DIMACS Implementation Challenge-Shortest Paths. URL: http://www.dis.uniromal.it/challenge9/download.shtml (дата обращения: 16.07.2012).

39. Abraham I., Neiman O. Using Petal-Decompositions to Build a Low Stretch Spanning Tree // Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 2012. P. 395-406.

40. Aggarwal A., Klawe M., Moran S., Shor P., Wilber R. Geometric Applications of a Matrix Searching Algorithm // Proceedings of the second annual symposium on Computational geometry, 1986. P. 285-292.

41. Aingworth D., Chekuri C., Motwani R. Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication) // Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, 1996. P. 547-553.

42. Albert R., Jeong H., Barabasi A. Internet: Diameter of the World-Wide Web // Nature. 1999. Vol. 401(6749). P. 130-131.

43. Aljazzar H., Leue S. K*: A Heuristic Search Algorithm for Finding the k Shortest Paths // Artificial Intelligence. 2011. Vol. 175(18). P. 2129-2154.

44. Alon N., Galil Z., Margalit O. On the Exponent of the All Pairs Shortest Path Problem // Journal of Computer and System Sciences. 1997. Vol. 54(2). P. 255-262.

45. Althofer I., Das G., Dobkin D., Joseph D., Soares J. On Sparse Spanners of Weighted Graphs // Discrete & Computational Geometry. Vol. 9(1). 1993. P. 81-100.

46. Andersson M., Gudmundsson J., Levcopoulos C. Restricted Mesh Simplification Using Edge Contractions // Proceedings of the 12th annual international conference on Computing and Combinatorics, 2006. P. 196-204.

47. Andreev K., Racke H. Balanced graph partitioning // Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures. 2004. P. 120— 124.

48. Awerbuch B., Berger B., Cowen L., Peleg D. Near-Linear Cost Sequential and Distributed Constructions of Sparse Neighborhood Covers // Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993. P. 638-647.

49. Backstrom L., Dwork C., Kleinberg J. Wherefore art thou r3579x?: Anonymized Social Networks, Hidden Patterns, and Structural Steganography // Proceedings of the 16th international conference on World Wide Web, 2007. P. 181-190.

50. Bannister M.J., Eppstein D. Randomized Speedup of the Bellman-Ford Algorithm // Proceedings of the Meeting on Analytic Algorithmics & Combinatorics, 2012. P. 4147.

51. Bansal N., Blum A., Chawla S. Correlation Clustering // Machine Learning. 2004. Vol. 56. P. 89-113.

52. Bast H., Funke S., Sanders P., Schultes D. Fast Routing in Road Networks with Transit Nodes // Science. 2007. Vol. 316(5824) P. 566.

53. Baswana S., Goyal V., Sen S. All-Pairs Nearly 2-Approximate Shortest Paths in 0(n2polylogn) Time // Theoretical Computer Science. 2009 Vol. 410(1). P. 84-93.

54. Baswana S., Kavitha T. Faster Algorithms for All-Pairs Approximate Shortest Paths in Undirected Graphs // SIAM Journal on Computing. 2010. Vol. 39(7). P.2865-2896.

55. Batson J., Spielman D.A., Srivastava N., Teng S. Spectral Sparsification of Graphs: Theory and Algorithms // Communications of the ACM. 2013. Vol. 56(8). P. 87-94.

56. Baues O., Peyerimhoff N. Curvature and Geometry of Tessellating Plane Graphs // Discrete and Computational Geometry. 2001. Vol. 25(1). P. 141-159.

57. Bellman R. On a Routing Problem // Quarterly of Applied Mathematics. 1958. Vol. 16. P. 87-90.

58. Benczur A.A., Karger D.R. Approximating s-t Minimum Cuts in 0(n2) Time // Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 1996. P. 47-55.

59. Ben-Moshe B., Bhattacharya B.K., Shi Q., Tamir A. Efficient Algorithms for Center Problems in Cactus Networks // Theoretical Computer Science. 2007. Vol. 378(3). P. 237-252.

60. Berman P., Kasiviswanathan S.P. Faster Approximation of Distances in Graphs // Algorithms and Data Structures. Lecture Notes in Computer Science. 2007. Vol. 4619. P. 541-552.

61. Boitmanis K., Freivalds K., Ledins P., Opmanis R. Fast and Simple Approximation of the Diameter and Radius of a Graph // Proceedings of the 5th international conference on Experimental Algorithms, 2006. P. 98-108.

62. Boldi P., Rosa M., Vigna S. HyperANF: approximating the neighbourhood function of very large graphs on a budget // Proceedings of the 20th international conference on World wide web. New York: ACM, 2011. P. 625-634.

63. Bonchi F., Morales G.D.F., Gionis A., Ukkonen A. Activity Preserving Graph Simplification // Data Mining and Knowledge Discovery. 2013. Vol. 27(3). P. 321-343.

64. Bonneau J., Anderson J. et al. Eight Friends Are Enough: Social Graph Approximation via Public Listings // Proceedings of the Second ACM EuroSys Workshop on Social Network Systems - New York: ACM, 2009. P. 13-18.

65. Brander A.W., Sinclair M.C. A Comparative Study of k-Shortest Path Algorithms // Proceedings of 11th UK Performance Engineering Workshop, 1995. P. 370-379.

66. Brodai G.S. Worst-Case Efficient Priority Queues // Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, 1996. P. 52-58.

67. Castroa A., Mollard M. The Eccentricity Sequences of Fibonacci and Lucas Cubes // Discrete Mathematics. 2012. Vol. 312(5). P.1025-1037.

68. Chabrier A. Vehicle Routing Problem with Elementary Shortest Path Based Column Generation // Computers and Operations Research. 2006. Vol. 33(10). P. 29722990.

69. Chamberlain B. Graph Partitioning Algorithms for Distributing Workloads of Parallel Computations // Technical Report UW-CSE-98-10-03, University of Washington, 1998. 32 p.

70. Chan T.M. All-Pairs Shortest Paths for Unweighted Undirected Graphs in O(mn) Time // ACM Transactions on Algorithms. 2012. Vol. 8 (4).

71. Chan T.M. More Algorithms for All-Pairs Shortest Paths in Weighted Graphs // Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. -New York: ACM, 2007. P. 590-598.

72. Chepoi V., Dragan F. ET AL. Center and Diameter Problems in Plane Triangulations and Quadrangulations // Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 2002. P. 346-355.

73. Chepoi V.D., Dragan F.F. Linear-Time Algorithm for Finding a Central Vertex of a Chordal Graph // Proceedings of the second Annual European Symposium Algorithms, 1994. P. 159-170.

74. Chevalier C., Safro I. Comparison of Coarsening Schemes for Multilevel Graph Partitioning // Learning and Intelligent Optimization, Springer-Verlag Berlin, Heidelberg, 2009. P. 191-205.

75. Chung F., Zhao W. Ranking and Sparsifying a Connection Graph // Proceedings of the 9th international conference on Algorithms and Models for the Web Graph, 2012. P. 66-77.

76. Cohen E. Fast Algorithms for Constructing /-Spanners and Paths with Stretch t II SIAM Journal on Computing. 1999. Vol. 28(1). P. 210-236.

77. Cohen E. Polylog-time and Near-Linear Work Approximation Scheme for Undirected Shortest Paths // Journal of the ACM. 2000. Vol. 47(1). P. 132-166.

78. Cohen E., Zwick U. All-Pairs Small-Stretch Paths // Journal of Algorithms. 2001. Vol. 38(2). P.335-353.

79. Cooke K., Halsey E. The Shortest Route Through a Network with Time-Dependent Internodal Transit Times // Journal of Mathematical Analysis and Applications. 1996. Vol.14. P. 493^198.

80. Coppersmith D., Winograd S. Matrix Multiplication via Arithmetic Progressions // Journal of Symbolic Computation - Special issue on computational algebraic complexity. 1990. Vol. 9(3). P. 251-280.

81. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms, Second Edition. MIT Press, 2001. 1202 p.

82. Corneil D., Dragan F., Habib M., Paul C. Diameter Determination on Restricted Graph Families // Discrete Applied Mathematics. 2001. Vol. 113(2-3). P. 143-166.

83. Corneil D.G., Dragan F.F., Kohler E. On the Power of BFS to Determine a Graph's Diameter // Networks. 2003. Vol. 42(4). P. 209-222.

84. Crescenzi P., Grossi R., Habib M., Lanzi L., Marino A. On Computing the Diameter of Real-World Undirected Graphs // Theoretical Computer Science. 2013 Vol. 514. P. 84-95.

85. Crescenzi P., Grossi R., Imbrenda C., Lanzi L., MarinoA. Finding the Diameter in Real-World Graphs // Algorithms - ESA 2010: Springer Berlin Heidelberg, 2010. P.302-313.

86. Crescenzi P., Grossi R., Lanzi L., Marino A. On Computing the Dameter of Real-World Directed (Weighted) Graphs // Proceedings of the 11th international conference on Experimental Algorithms, 2012. P. 99-110.

87. Cuninghame-Green R.A. The Absolute Centre of a Graph // Discrete Applied Mathematics. 1984. Vol. 7(3). P. 275-283.

88. Danezis G., Wittneben B. The Economics of Mass Durveillance and the Wuestionable Value of Snonymous Communications. Proceedings of the 5th Workshop on The Economics of Information Security // Proceedings of the 5th Workshop on The Economics of Information Security, 2006.

89. Dankelmann P., Erwin D., Goddard W., Mukwembi S., Swart H.C. A Characterisation of Eccentric Sequences of Maximal Outerplanar Graphs // The Australian Journal of Combinatorics. 2014. Vol. 58(3). P. 376-391.

90. Dankelmann P., Erwin D., Goddard W., Mukwembi S., Swart H.C. Eccentric Counts, Connectivity and Chordality // Information Processing Letters. 2012. Vol. 112(24). P. 944-947.

91. Dijkstra E.W. A note on two problems in connection with graphs // Numerische Mathematik 1. 1959. P. 83-89.

92. Dionne R. Etude et extension d'un algorithme de Murchland // INFOR. 1978. Vol. 16. P. 132-146.

93. Dor D., Halperin S., Zwick U. All Pairs Almost Shortest Paths // SIAM Journal on Computing. 1996. Vol. 29. P. 452-461.

94. Dorigo M. Ant Colonies for the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation. 1997. Vol. 1(1). P. 53-66.

95. Dragan F.F., Fomin F.V., Golovach P.A. Spanners in Sparse Graphs // Automata, Languages and Programming: Springer Berlin Heidelberg, 2008. P. 597-608.

96. Dreyfus S. An Appraisal of Some Shortest-Path Algorithms // Operations Research. 1969. Vol. 17(3). P. 395^112.

97. Driscoll J.R., Gabow H.N., Shrairman R., Tarjan R.E. Relaxed Heaps: an Alternative to Fibonacci Heaps with Applications to Parallel Vomputation Priority Queues and Dijkstra's Algorithm // Communications of the ACM. 1988. Vol. 31(11). P. 1343-1354.

98. Edelkamp S., Korf R.E. The Branching Factor of Regular Search Spaces // Proceedings of the fifteenth 'national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, 1998. P. 299-304.

99. Edge Graphs and Eccentricity Sequences [Электронный ресурс]. Режим доступа: http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%209.PDF

100.Elkin М. Computing Almost Shortest Paths // ACM Transactions on Algorithms. 2005. Vol. 1(2). P. 283-323.

101. Eisner U. Graph Partitioning - A Survey. Techn. Univ., 1997. 70 p.

102. Eppstein D. Finding the k Shortest Paths // SIAM Journal on Computing. 1999. Vol. 28(2). P. 652-673.

103.Feder Т., Motwani R.. Clique Partitions, Graph Compression and Speeding-Up Algorithms // Journal of Computer and System Sciences. 1995. Vol. 51. P. 261-272.

104. Fertin G., Hermelin D. et al. Common structured patterns in linear graphs: approximation and combinatorics // Proceedings of the 18th annual conference on Combinatorial Pattern Matching. 2007. P. 241-252.

105.Fiduccia C.M., Mattheyses R.M. A Linear-Time Heuristic for Improving Network Partitions // Proceedings of the 19th Design Automation Conference. 1982. P. 175-181.

106. Floyd R.W. Algorithm 97: Shortest Path // Communications of the ACM. 1962. Vol. 5, N6. P. 345.

107. Ford L.R. Jr. Network Flow Theory // RAND Corporation, 1956. 13 p.

108. Fortunato S. Community Detection in Graphs [Электронный ресурс] - Режим доступа: http://arxiv.org/abs/0906.0612.

109.Fredman M.L., Tarjan R.E. Fibonacci Heaps and Their Use in Improved Network Optimization Algorithms // Journal of the ACM. 1987. Vol. 34(3). P. 596-615.

110. Frieze A. M., Kannan R. The Regularity Lemma and Approximation Schemes for Dense Problems // Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996. P. 12-20.

111.Fung W.S., Hariharan R., Harvey N.J.A., Panigrahi D. A General Framework for Graph Sparsification // Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011. P. 71-80.

112. Gabow H.N. Scaling Algorithms for Network Problems // Journal of Computer and System Sciences. 1985. Vol. 31(2). P. 148-168.

113. Gabow H.N., Tarjan R.E. Faster Scaling Algorithms for Network Problems // SIAM Journal on Computing. 1989. Vol. 18(5). P. 1013-1026.

114. Galil Z., Margalit O. All Pairs Shortest Distances for Graphs with Small Integer Length Edges // Information and Computation. 1997. Vol. 134(2). P. 103-139.

115. Galil Z., Margalit O. All Pairs Shortest Paths for Graphs with Small Integer Length Edges // Journal of Computer and System Sciences. 1997. Vol. 54. P. 243-254.

116.Gallo G. Reoptimization Procedures in Shortest Path Problems // Rivista di Matematica per le Scienze Economiche e Sociali. 1980. Vol. 3(1). P. 3-13.

117.Garey M.R., Johnson D.S., Stockmeyer L. Some Simplified NP-Complete Graphs Problems // Proceedings of the sixth annual ACM symposium on Theory of computing, 1974. P. 47-63.

118.Geerts F., Revesz P. On-Line Maintenance of Simplified Weighted Graphs for Efficient Distance Queries // Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, 2006. P. 203-210.

119. Geisberger R., Sanders P., Schultes D., Delling D. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks // Proceedings of the 7th international conference on Experimental algorithms, 2008. P. 319-333.

120. Giotis I., Guruswami V. Correlation Clustering With a Fixed Number of Clusters // Theory of Computing. 2006. Vol. 2(1). P. 249-266.

121.Gjoka M., Kurant M., Butts C.T., Markopoulou A. Walking in Facebook: A Case Study of Unbiased Sampling of OSNs // Proceedings of the 29th conference on Information communications, 2010. P. 2498-2506.

122. Glattfelder J.B. Backbone of Complex Networks of Corporations: The Flow of Control // Decoding Complexity. Springer Berlin Heidelberg, 2013. P. 67-93.

123. Goldberg A.V. Scaling Algorithms for the Shortest Paths Problem // Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. 1993. P. 222231.

124. Goldberg A.V., Tarjan R.E. Expected Performance of Dijkstra's Shortest Path Algorithm // Technical Report TR-530-96, Princeton University, 1996. 7 p.

125. Goldreich O., Goldwasser S., Ron D. Property Testing and its Connection to Learning and Approximation // Journal of the ACM. 1998. Vol. 45(4). P. 653-750.

126. Gutin G., Yeo A., Zverovich A. Traveling Salesman Should Not be Greedy: Domination Analysis of Greedy-Type Heuristics for the TSP // Discrete Applied Mathematics. 2002. Vol. 117(1-3). P. 81-86.

127. Haeupler B., Sen S., Tarjan R.E. Rank-Pairing Heaps // SIAM Journal on Computing. 2011. Vol. 40(6). P. 1463-1485.

128. Hagen L., Kahng A. New spectral methods for ratio cut partitioning and clustering // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. -Vol. 11(9). 1992. P. 1074-1085.

129. Hagerup T. Improved Shortest Paths on the Word RAM // Proceedings of the 27th International Colloquium on Automata, Languages and Programming. 2000. P. 61-72.

130. Hagerup T. Sorting and Searching on the Word RAM // Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, 1998. P. 366-398.

131.Hakimi S.L. Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph // Operations Research. 1964. Vol. 12(3). P. 450^159.

132. Haider A. The Method of Competing Links // Transportation Science. 1970. Vol. 4(1). P.36-51.

133. Han Y. An 0(n3(loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Path // Algorithmica. 2008. Vol. 51(4). P. 428-434.

134. Han Y., Takaoka T. An 0(n31oglogn/log2n) Time Algorithm for All Pairs Shortest Paths // Proceedings of the 13th Scandinavian conference on Algorithm Theory, 2012. P. 131-141.

135. Han Y., Thorup M. Integer Sorting in 0(nsqrt(loglogn)) Expected Time and Linear Space // Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002. P. 135-144.

136. Handler G.Y. Minimax Location of a Facility in an Undirected Tree Graph // Transportation Science. 1973. Vol. 7(3). P. 287-293.

137. Handler G.Y., Zang I. A Dual Algorithm for the Constrained Shortest Path Problem//Networks. 1980. Vol. 10(4). P.293-309.

138. Harary F. A Survey of the Reconstruction Conjecture // Proceedings of the Capital Conference on Graph Theory and Combinatorics. 1973. P. 18-28.

139. Harary F. On the Reconstruction of a Graph From a Collection of Subgraphs // Theory of Graphs and its Applications, 1963. P. 47-52.

140. Hardt M., Srivastava N., Tulsiani M. Graph Densification // Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, 2012. P. 380-392.

141. Hart P.E., Nilsson N.J., Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths // IEEE Transactions on Systems Science and Cybernetics. 1968. Vol. 4(2). P. 100-107.

142. Heggernes P., Hof P. van't, Jansen B.M.P., Kratsch S., Villanger Y. Parameterized Complexity of Vertex Deletion into Perfect Graph Classes // Proceedings of 18th International Symposium, 2011. P. 240-251.

143.Hoede C., Veldman H.J. Contraction Theorems in Hamiltonian Graph Theory // Discrete Mathematics. 1981. Vol. 34(1). P. 61-67.

144. Hof P. van't, Kaminski M., Paulusma D., Szeider S., Thilikos D.M. On Graph Contractions and Induced Minors // Discrete Applied Mathematics. 2012. Vol. 160. P. 799-809.

145. Hu P., Lau W.C. A Survey and Taxonomy of Graph Sampling [Электронный ресурс] - Режим доступа: http://arxiv.org/abs/1308.5865.

146.Huffner F., Betzler N., Niedermeier R. Optimal Edge Deletions for Signed Graph Balancing // Proceedings of 6th International Workshop, 2007. P. 297-310. 147.1rnich S., Desaulniers G. Shortest Path Problems with Resource Constraints // Column Generation: Springer US, 2005. P. 33-65.

148. Irnich S., Villeneuve D. The Shortest Path Problem with Resource Constraints and k-Cycle Elimination for k>3 // INFORMS Journal on Computing. 2006. Vol. 18(3). P. 391-406.

149. Jacob J., Jentsch, M. et al. Detecting hierarchical structure in molecular characteristics of disease using transitive approximations of directed graphs // Bioinformatics. 2008. Vol. 24(7). P. 995-1001.

150. Johnson D.B. Efficient Algorithms for Shortest Paths in Sparse Networks // Journal of the ACM. 1977. Vol. 24(1). P. 1-13.

151.Kaminski M., Paulusma D., Thilikos D.M. Contractions of Planar Graphs in Polynomial Time // Proceedings of 8th Annual European Symposium, 2010. P. 122133.

152.Kang U., Tsourakakis C.E., Appel A.P., Faloutsos C., Leskovec J. Hadi: Mining Radii of Large Graphs // ACM Transactions on Knowledge Discovery from Data. 2011. Vol. 5(2).

153. Kaplan H., Tarjan R.E. New Heap Data Structures // Technical Report TR-597-99, Princeton University, 1999. 16 p.

154. Karger D.R., Koller D., Phillips S.J. Finding the Hidden Path Time Bounds for All-Pairs Shortest Paths // SIAM Journal on Computing. 1993. Vol. 22(6). P. 1199-1217.

155.Karp R.M. Reducibility among Combinatorial Problems // Complexity of Computer Computations: Springer US, 1972. P. 85-103.

156. Karypis G., Kumar V. A Fast and High Quality Multilevel scheme for Partitioning Irregular Graphs // SIAM Journal on Scientific Computing. 1998. Vol. 20(1). P. 359392.

157. Karypis G., Kumar V. Multilevel k-way Partitioning Scheme for Irregular Graphs // Journal of Parallel and Distributed Computing. 1998. Vol. 48(1). P. 96-129.

158. Kaufman D.E., Smith R.L. Fastest Paths in Time-Dependent Networks for Intelligent Vehicle-Highway Systems Application // Journal of Intelligent Transportation Systems. 1993. Vol. 1(1). P. 1-11.

159. Kelly P.J. A Congruence Theorem for Trees // Pacific Journal of Mathematics. 1957. Vol. 7. P. 961-968.

160. Kernighan B., Lin S. An Efficient Heuristic Procedure for Partitioning Graphs // The Bell system technical journal. Vol. 40, №1. 1970. P. 291-307.

161. Kim J., Hwang I., Kim Y.-H., Moon B.-R. Genetic Approaches for Graph Partitioning: a Survey // Proceedings of the 13th annual conference on Genetic and evolutionary computation, 2011. P. 473^180.

162. Kleinberg J. The Small-World Phenomenon: An Algorithm Perspective // Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000. P. 163-170.

163.Knuth D. The Art of Computer Programming, Vol. 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. 800 p.

164.Kolla A., Makarychev Y., Saberi A., Teng S. Subgraph Sparsification and Nearly Optimal Ultrasparsifiers // Proceedings of the forty-second ACM symposium on Theory of computing, 2010. P. 57-66.

165.Koutis I., Levin A. et al. Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices // Proceedings STACS. 2012. P. 266-277.

166.Kratsch S., Schweitzer P. Isomorphism for Graphs of Bounded Feedback Vertex Set Number // Proceedings of 12th Scandinavian Symposium and Workshops on Algorithm Theory, 2010. P. 81-92.

167. Krishnamurthy V., Faloutsos M., Chrobak M., Lao L., Cui J.-H., Percus A.G. Reducing Large Internet Topologies for Faster Simulations // Proceedings of the 4th IFIP-TC6 international conference on Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communication Systems, 2005. P. 328-341.

168. Kuhn F., Moscibroda T. et al. Unit disk graph approximation // Proceedings of the 2004 joint workshop on Foundations of mobile computing. 2004. P. 17-23.

169. Kung U., Tsourakakis C.E., Appel A.P., Faloutsos C., Leskovec J. Radius Plots for Mining Tera-byte Scale Graphs: Algorithms, Patterns, and Observations // SIAM International Conference on Data Mining 2010. 2010. P.548-558.

170. Lanzi L. Complex Networks: Algorithms, Analysis, and Models, PhD dissertation. University of Florence, 2012.

171.Lawler E.L. A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem // Management Science. 1972. Vol. 18(7). P. 401-405.

172.Lawler E.L. Improvements in Efficiency: Yen's Modifications // Combinatorial Optimization: Networks and Matroids, 2001. P. 76-77.

173.Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G., Shmoys D.B. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, 1985. 476 p.

174.Leskovec J., Faloutsos C. Sampling from Large Graphs // Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 2006. P. 631-636.

175.Leskovec J., Kleinberg J., Faloutsos C. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations // Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, 2005. P. 177-187.

176.Leskovec J., Lang K., Dasgupta A., Mahoney M. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Dened Clusters // Internet Mathematics. 2009. Vol. 6(1). P. 29-123.

177. Lesniak L. Eccentric Sequences in Graphs // Periodica Mathematica Hungarica. 1975. Vol. 6(4). P. 287-293.

178. Levin A., Paulusma D., Woeginger G.J. The Complexity of Graph Contractions // Graph-Theoretic Concepts in Computer Science, Springer Berlin Heidelberg, 2003. P. 322-333.

179. Lin S., Kernighan B.W. An Effective Heuristic Algorithm for the Traveling-Salesman Problem // Operations Research. 1973. Vol. 21(2). P. 498-516.

180. Long B., Xiaoyun X. et al. Community Learning by Graph Approximation // Proceeding ICDM '07 Proceedings of the 2007 Seventh IEEE International Conference on Data Mining. 2007. P. 232-241.

181. Lyndon R.C. A Maximum Principle for Graphs // Journal of Combinatorial Theory. 1967. Vol. 3(1). P. 34-37.

182. Magnien С., Latapy M., Habib M. Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs // Journal of Experimental Algorithmics. 2009. Vol. 13.

183. Mathioudakis M., Bonchi F., Castillo C., Gionis A., Ukkonen A. Sparsification of Influence Networks // Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011. P. 529-537.

184. Miltersen P.B. Lower Bounds for Static Dictionaries on RAMs with Bit Operations but no Multiplication // Automata, languages and programming. Springer, 1996. P. 442453.

185.Mislove A., Marcon M., Gummadi K.P., Druschel P., Bhattacharjee B. Measurement and Analysis of Online Social Networks // Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, 2007. P. 29^12.

186. Moore E. The shortest path through a maze. New York: Bell Telephone System, 1959. 8 p.

187. Murchland J.D. A Fixed Matrix Method for All Shortest Distances in a Directed Graph and for the Inverse Problem. PhD dissertation. University of Karlsruhe, Karlsruhe, 1970.

188. Nannicini G., Liberti L. Shortest Paths on Dynamic Graphs // International Transactions in Operational Research. 2008. Vol. 15(5). P. 551-563.

189. OpenStreetMap [Электронный ресурс] - Режим доступа: http://www.openstreetmap.org/.

190.0rda A., Rom R. Shortest-Path And Minimum-Delay Algorithms In Networks With Time-Dependent Edge-Length // Journal of the ACM. 1990. Vol. 37(3). P. 607625.

191. Palmer C.R., Gibbons P.B., Faloutsos C. ANF: a Fast and Scalable Tool for Data Mining in Massive Graphs // Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2002. p. 81-90.

192. Pettie S. A New Approach to All-Pairs Shortest Paths on Real-Weighted Graphs // Theoretical Computer Science. 2004. Vol. 312(1), P. 47-74.

193. Pettie S. An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree Verification Problem // Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002. P. 155-163.

194. Pettie S., Ramachandran V. A Shortest Path Algorithm for Real-Weighted Undirected Graphs // SIAM Journal on Computing. 2005. Vol. 34(6). P. 1398-1431.

195.Plesnik J. A Heuristic for the p-Center Problems in Graphs // Discrete Applied Mathematics. 1987. Vol. 17(3). P. 263-268.

196.Pohl I. Bi-directional Search // Machine Intelligence. 1971. Vol. 6. P. 127-140.

197. Qi Z., Xiao Y., Wang H., Shao B. Toward a Distance Oracle for Billion-Node Graphs // PVLDB. 2013. Vol.7(l). P. 61-72.

198. Raman R. Priority Queues: Small, Monotone and Trans-Dichotomous // Algorithms - ESA '96: Springer Berlin Heidelberg, 1996. P.121-137.

199. Raman R. Recent Results on the Single-Source Shortest Paths Problem // ACM SIGACTNews. 1997. Vol. 28(2). P. 81-87.

200. Reddy K.R., Iyer K.V. All-Pairs Shortest-Paths Problem for Unweighted Graphs in 0(n21ogn) Time // International Journal of Computational and Mathematical Sciences. 2009. Vol. 3(5). P. 411-417.

201.Rimscha von M. Reconstructibility and Perfect Graphs // Discrete Mathematics. 1983. Vol. 47. P. 283-291.

202.Roditty L., Williams V.V. Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs // Proceedings of the forty-fifth annual ACM symposium on Theory of computing. 2013. P. 515-524.

203. Ruan N., Jin R., Huang Y. Distance Preserving Graph Simplification // Proceedings of the 2011 IEEE 11th International Conference on Data Mining, 2011. P. 1200-1205.

204. Russell S., Norvig P. Artificial Intelligence: A Modern Approach (3rd Edition). Prentice Hall, 2009. 1152 p.

205.Safro I., Sanders P., Schulz C. Advanced Coarsening Schemes for Graph Partitioning // Proceedings of the 11th international conference on Experimental Algorithms, 2012. P. 369-380.

206. Sala A., Cao L., Wilson C., Zablit R., Zheng H., Zhao B. Measurement-Calibrated Graph Models for Social Network Experiments // Proceedings of the 19th ACM International Conference on the World Wide Web (WWW), 2010. P. 861-870.

207. Sanders P., Schultes D. Highway Hierarchies Hasten Exact Shortest Path Queries // Proceedings of the 13th annual European conference on Algorithms Pages, 2005. P. 568-579.

208. Sankowski P. Shortest Paths in Matrix Multiplication Time // Algorithms - ESA 2005: Springer Berlin Heidelberg. Berlin, 2005. P.770-778.

209. Satuluri V., Parthasarathy S., Ruan Y. Local Graph Sparsification for Scalable Clustering // Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, 2011. P. 721-732.

210. Seidel R. On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs // Journal of Computer and System Sciences. 1995. Vol. 5. P. 400^03.

211. Shamir R., Sharan R., Tsur D. Cluster Graph Modification Problems // Discrete Applied Mathematics - Discrete Mathematics & Data Mining. 2004. Vol 144(1-2). P. 173-182.

212. Shepherdson J.C., Sturgis H.E. Computability of Recursive Functions // Journal of the ACM. 1963. Vol. 10(2). P. 217-255.

213. Shoshan A., Zwick U. All Pairs Shortest Paths in Undirected Graphs with Integer Weights // Proceedings of the 40th Annual Symposium on Foundations of Computer Science. Washington: IEEE Computer Society, 1999. P. 605-614.

214. Spielman D.A., Teng S. Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems // Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, 2004. P. 81-90.

215.SPOJ Problem Set (classical). 3405. Almost Shortest Path. Problem code: SAMER08A [Электронный ресурс] - Режим доступа: http://www.spoj.com/problems/SAMER08A/.

216.Sprague А.Р. 0(1) Query Time Algorithm for All Pairs Shortest Distances on Permutation Graphs // Discrete Applied Mathematics. 2007. Vol. 155(3). P. 365-373.

217. Stachniss С., Kretzschmar H. Pose Graph Compression for Laser-Based SLAM // Proceedings the International Symposium of Robotics Research, 2011.

218. Takaoka T. Sub-Cubic Cost Algorithms for the All Pairs Shortest Path Problem // Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science, 1995. P. 323-343.

219. Takes F.W., Kosters W.A. Computing the Eccentricity Distribution of Large Graphs // Algorithms. 2013. Vol. 6(1). P. 100-118.

220. Takes F.W., Kosters W.A. Determining the diameter of small world networks // Proceedings of the 20th ACM international conference on Information and knowledge management. New York: ACM, 2011. P. 1191-1196.

221. Tangwongsan K. Lecture 18 - Graph Contraction II: Connectivity and MSTs [Электронный ресурс] - Режим доступа: http://www.cs.cmu.edu/afs/cs/academic /class/15210-s 12/www/lectures/lecture 18 .pdf.

222. Tarjan R.E. Data Structures and Network Algorithms // Society for Industrial and Applied Mathematics, 1983. 131 p.

223. The Boost Graph Library 1.54.0 [Электронный ресурс] - Режим доступа: http://www.boost.org/doc/libs/l_54_0/libs/graph/doc/.

224. Thorup М. Integer Priority Queues with Decrease Key in Constant Time and The Single Source Shortest Paths Problem // Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. 2003. P. 149-158.

225. Thorup M. On RAM Priority Queues // Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms. 1996. P. 59-67.

226. Thorup M. Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time // Journal of the ACM. 1999. Vol. 46(3). P. 362-394.

227. Thorup M., Zwick U. Approximate Distance Oracles // Proceedings of the thirty-third annual ACM symposium on Theory of computing, 2001. P. 183-192.

228.Toivonen H., Mahler S., Zhou F. A Framework for Path-Oriented Network Simplification // Proceedings of 9th International Symposium, 2010. P. 220-231.

229. Tumminello M., Aste Т., Matteo T.D., Mantegna R.N. A Tool for Filtering Information in Complex Systems // Proceedings of the National Academy of Sciences of the United States of America. 2005. Vol. 102(30). P. 10421-10426.

230. Urakov A.R., Timeryaev T.V. All-pairs shortest paths algorithm for high-dimensional sparse graphs // Computer Science and Information Technology. Vol. 1(3), pp. 233-237.

231. Wagner K. Uber eine Eigenschaft der ebenen Komplexe // Mathematische Annalen. 1937. P. 570-590.

232. Wang Т., Chen Y., Zhang Z., Xu Т., Jin L., Hui P., Deng В., Li X. Understanding Graph Sampling Algorithms for Social Network Analysis // Proceedings of the 2011 31st International Conference on Distributed Computing Systems Workshops, 2011. P. 123-128.

233. Warshall S. A Theorem on Boolean Matrices // Journal of the ACM. 1962. Vol. 9(1). P. 11-12.

234. Wasserman S., Faust K. Social Network Analysis: Methods and Applications. Cambridge Press, 1994. 857 p.

235. Williams J.W.J. Algorithm 232 - Heapsort // Communications of the ACM. 1964. Vol. 7(6) P. 347-348.

236. Xu H., Chen Z., Rajagopal S., Arunapuram S. Solving a Practical Pickup and Delivery Problem // Transportation Science. 2003. Vol. 37(3). P. 347-364.

237. Yannakakis M. Node and Edge Deletion NP-Complete Problems // Proceedings of the tenth annual ACM symposium on Theory of computing, 1978. P. 253-264.

238. Yen J.Y. An Algorithm for Finding Shortest Routes From All Source Nodes to a Given Festination in General Networks // Quarterly of Applied Mathematics. 1970. Vol. 27. P.526-530.

239. Yen J.Y. Finding the К Shortest Loopless Paths in a Network // Management Science. 1971. Vol. 17(11). P. 712-716.

240. Yuster R. Computing the Diameter Polynomially Faster than APSP [Электронный ресурс]. Режим доступа: http://arxiv.org/abs/1011.6181

241. Zwick U. All Pairs Lightest Shortest Paths // Proceedings of the 31th Annual ACM Symposium on Theory of Computing. 1999. P. 61-69.

242. Zwick U. All Pairs Shortest Paths in Weighted Directed Graphs - Exact and Almost Exact Algorithms // Proceedings of the 39th Annual Symposium on Foundations of Computer Science. 1998. P. 310-319.

243. Zwick U. Exact and Approximate Distances in Graphs - A Survey // Algorithms -ESA 2001: Springer Berlin Heidelberg, 2001. P. 33-48.

Приложение 1 Среднее время решения задач аппроксимации разными алгоритмами

Таблица П1. Среднее время решения в секундах второй задачи аппроксимации алгоритмом АР2 с размерностью аппроксимирующих графов равной 90%, 75% и

50% от размерности исходного графа для групп USA120, QSM120 и RU

Группа графов *=[0,9-|Fl] *=[0,75-|F|] *=[0,5-|F|] Группа графов k=[ 0,9-\V\] И 0,75-И]

USA 1 0,134 0,198 0,413 OSM 1 0,111 0,166 0,336

USA 2 0,471 0,746 1,63 OSM 2 0,391 0,631 1,35

USA 3 1,03 1,67 3,56 OSM 3 0,856 1,39 2,86

USA 4 1,83 2,98 6,41 OSM 4 1,45 2,39 5,08

USA 5 2,85 4,68 9,96 OSM 5 2,29 3,84 7,94

USA 6 4,06 6,69 14,2 OSM 6 3,23 5,46 11,6

USA 7 5,62 9,31 19,7 OSM 7 4,56 7,8 16,6

USA 8 7,26 12,3 25,2 OSM 8 5,82 10 21,1

USA 9 9,3 15,5 32,2 OSM 9 7,43 12,8 26,9

USA 10 11,9 19,7 41,1 OSM 10 9,25 16 33,2

USA 15 26,9 44,9 93 OSM 15 21 36,7 74,5

USA 20 49 81,4 172 OSM 20 40,4 69,4 140

RU 0,554 0,897 2,05

Таблица П2. Среднее время решения в секундах второй задачи аппроксимации алгоритмом А2 с размерностью аппроксимирующих графов равной 90%, 75% и

50% от размерности исходного графа для групп ША1_20, 08М120 и БШ

Группа графов *=[0,75-|F|] k=[ 0,5-И] Группа графов И0,9-И] *=[0,75-И] И0.5-И]

USA 1 0,04 0,038 0,04 OSM 1 0,036 0,034 0,037

USA 2 0,125 0,135 0,123 OSM 2 0,117 0,122 0,116

USA 3 0,288 0,255 0,283 OSM 3 0,245 0,261 0,253

USA 4 0,491 0,479 0,479 OSM 4 0,437 0,444 0,456

USA 5 0,656 0,729 0,712 OSM 5 0,652 0,674 0,672

USA 6 0,967 0,967 1,01 OSM 6 0,948 0,964 0,966

USA 7 1,24 1,36 1,31 OSM 7 1,32 1,36 1,3

USA 8 1,71 1,77 1,65 OSM 8 1,7 1,78 1,77

USA 9 2,2 2,24 2,13 OSM 9 2,25 2,43 2,42

USA 10 2,88 2,93 2,9 OSM 10 2,65 2,71 2,8

USA 15 6,09 6,23 6,35 OSM 15 6,15 6,27 6,65

USA 20 10,3 11,6 11,8 OSM 20 10,5 10,2 10,9

RU 0,157 0,158 0,156

Таблица ПЗ. Среднее число итераций БМ-эвристики при решении второй задачи аппроксимации алгоритмом АР2 с размерностью аппроксимирующих графов равной 90%, 75% и 50% от размерности исходного графа для групп И8А1 __20,

08М1 20 и Яи

Группа графов A=[0,9-|F|] fc=[0,75-| F|] И0,5-|Р|] Группа графов И0,9-| PI] И0.75-И] И0.5-И]

USA 1 3,56 3,33 4,11 08М 1 5Д 5,3 4,4

USA 2 3,11 3,56 4,22 08М 2 3,4 5,7 7Д

USA 3 3,11 3,56 4,67 08М 3 5,8 4,1 4,4

USA 4 4,44 4,44 5,11 08М 4 5,1 5,2 6,7

USA 5 3,89 5,11 4 08М 5 4,1 6,2 4,2

USA 6 3,56 3,78 4,78 08М 6 5,5 5,2 7,3

USA 7 4,11 4,89 5,78 08М 7 4,5 5,3 5

USA 8 4,33 6,44 5,22 08М 8 6,6 4,7 5,3

USA 9 3,67 4,33 3,89 08М 9 5,2 7,7 7

USA 10 3,67 3,89 3,56 08М 10 6,1 8,6 7,8

USA 15 3,44 5 5 08М 15 6,4 7,8 8,4

USA 20 4 5,44 5,56 08М 20 5,7 9,3 6,3

RU 2,04 2,90 2,94

Таблица П4. Среднее число решений первой задачи аппроксимации при аппроксимации алгоритмом А2 с размерностью аппроксимирующих графов равной 90%, 75% и 50% от размерности исходного графа для групп И8А1_20,

08М1 20 и Яи

Группа графов Ä=[ 0,9-1 F|] k=[ 0,75-| Fl] И0.5-И] Группа графов И 0,9-И] *=[ 0,75-| *=[0,5-И]

USA 1 13,3 13 10,6 08М 1 12,6 12,3 11

USA 2 13,1 14,2 12,6 08М 2 14,1 13,5 11,8

USA 3 15,2 13,8 13,7 08М 3 13,8 14 13,3

USA 4 14,6 14,3 13,8 08М 4 14,2 14,2 13,4

USA 5 15,2 15,9 14,4 08М 5 14,5 14,5 13,7

USA 6 15,6 14,9 14,8 08М 6 15,7 15,2 13,8

USA 7 15,2 16,1 14,7 08М 7 15,4 15,4 14,5

USA 8 15,3 16,4 15,2 08М 8 16,1 16 14

USA 9 16,2 15,8 14,8 08М 9 15,8 16,3 14,8

USA 10 16,4 16,9 15,4 08М 10 16,7 16,2 15,3

USA 15 17 16,7 16,3 08М 15 17,4 16,6 16

USA 20 17,2 17,7 16,8 08М 20 16,8 16,3 15,9

RU 16,2 15,3 13,9

Таблица П5. Среднее отношений ошибки аппроксимации начального разбиения к ошибке аппроксимации после улучшения разбиения БМ-эвристикой для алгоритма АР2 с размерностью аппроксимирующих графов равной 90%, 75% и 50% от размерности исходного графа для групп 118А1_20, 08М120 и БШ

Группа графов И0.9-И] *=[0,75-|F|] И0.5-И1 Группа графов *=[0,9-1*11 НО,75-И] И0,5-И]

USA 1 1,95 2,15 2,81 08М 1 2,57 2,6 3,28

USA 2 1,9 2,16 2,5 08М 2 2,87 3,15 2,99

USA 3 1,99 2,29 2,79 08М 3 2,22 2,86 3,75

USA 4 2,31 2,39 2,79 08М 4 2,72 3,12 3,42

USA 5 1,9 2,75 2,90 08М 5 2,46 3,04 3,12

USA 6 2,18 2,4 2,63 08М 6 3,17 3,27 4,11

USA 7 2,35 2,56 2,84 08М 7 2,34 3 2,85

USA 8 2,38 2,93 3,01 08М 8 2,44 2,83 3,54

USA 9 2,37 2,45 3,3 08М 9 2,93 4,07 3,86

USA 10 1,96 2,28 2,91 08М 10 3,47 3,8 4,11

USA 15 2,3 2,56 2,65 08М 15 2,98 3,43 3,68

USA 20 2,28 2,58 2,91 08М 20 2,75 4,16 3,54

RU 2,80 2,43 2,23