Проблема с самым широким путем

На этом графике самый широкий путь от Мэлдона до Фиринга имеет пропускную способность 29 и проходит через Клактон, Типтри, Харвич и Блаксхолл.

В графовых алгоритмах самой широкой проблемой пути является проблема поиска пути между двумя назначенными вершинами во взвешенном графе , максимизирующая вес ребра минимального веса в пути. Проблема самого широкого пути также известна как проблема пути максимальной пропускной способности . Можно адаптировать большинство алгоритмов кратчайшего пути для расчета самых широких путей, изменив их так, чтобы они использовали расстояние до узкого места вместо длины пути. ^[1] Однако во многих случаях возможны еще более быстрые алгоритмы.

Например, в графе, представляющем соединения между маршрутизаторами в Интернете , где вес ребра представляет пропускную способность соединения между двумя маршрутизаторами, самой широкой проблемой пути является проблема поиска сквозного пути между двумя Интернет-маршрутизаторами. узлы, имеющие максимально возможную пропускную способность. ^[2] Наименьший вес ребра на этом пути известен как пропускная способность или пропускная способность пути. Помимо применения в сетевой маршрутизации, задача о максимально широком пути также является важным компонентом метода Шульце для определения победителя многосторонних выборов. ^[3] и был применен к цифровому композитингу , ^[4] анализ метаболических путей , ^[5] и вычисление максимальных потоков . ^[6]

Тесно связанная проблема, задача минимаксного пути или проблема кратчайшего пути с узким местом, требует поиска пути, который минимизирует максимальный вес любого из его ребер. Он имеет приложения, которые включают в себя планирование транспортировки . ^[7] Любой алгоритм для задачи о самом широком пути можно преобразовать в алгоритм для задачи о минимаксном пути или наоборот, изменив смысл всех сравнений весов, выполняемых алгоритмом, или, что то же самое, заменив каждый вес ребра его отрицанием.

Неориентированные графы

В неориентированном графе самый широкий путь может быть найден как путь между двумя вершинами максимального остовного дерева графа, а минимаксный путь может быть найден как путь между двумя вершинами минимального остовного дерева. ^[8]^[9]^[10] Из этой эквивалентности немедленно следует, что все пары широчайших путей в $n$ -вершинный неориентированный граф можно вычислить за время $O(n^{2})$ . ^[11]

В любом графе, ориентированном или неориентированном, существует простой алгоритм поиска самого широкого пути, если известен вес его ребра с минимальным весом: просто удалите все меньшие ребра и найдите любой путь среди оставшихся ребер, используя поиск в ширину или поиск в глубину . На основе этого теста также существует с линейным временем алгоритм для поиска самого широкого $пути s - t$ в неориентированном графе, который не использует максимальное остовное дерево. Основная идея алгоритма состоит в том, чтобы применить алгоритм поиска пути за линейное время к медианному весу ребра в графе, а затем либо удалить все меньшие ребра, либо сжать все большие ребра в зависимости от того, существует или нет путь. и рекурсивно использовать полученный меньший граф. ^[9]^[12]^[13]

Фернандес, Гарфинкель и Арбиол (1998) используют ненаправленные кратчайшие пути с узкими местами для формирования составных аэрофотоснимков , которые объединяют несколько изображений перекрывающихся областей. В подзадаче, к которой применима задача о самом широком пути, два изображения уже преобразованы в общую систему координат ; Оставшаяся задача — выбрать шов — кривую, проходящую через область перекрытия и отделяющую одно из двух изображений от другого. Пиксели на одной стороне стыка будут скопированы с одного изображения, а пиксели на другой стороне стыка — с другого изображения. В отличие от других методов композитинга, которые усредняют пиксели обоих изображений, этот метод создает достоверное фотографическое изображение каждой части фотографируемой области. Они взвешивают ребра сеточного графа с помощью числовой оценки того, насколько визуально заметен шов на этом ребре, и находят кратчайший путь узкого места для этих весов. Использование этого пути в качестве стыка, а не более традиционного кратчайшего пути, приводит к тому, что их система находит стык, который трудно различить во всех его точках, вместо того, чтобы позволить ей жертвовать большей видимостью в одной части изображения в пользу меньшей. видимость в другом месте. ^[4]

Решение задачи о минимаксном пути между двумя противоположными углами сеточного графа можно использовать для нахождения слабого расстояния Фреше между двумя многоугольными цепями . Здесь каждая вершина графа сетки представляет собой пару отрезков линии, по одному из каждой цепи, а вес ребра представляет собой расстояние Фреше, необходимое для перехода от одной пары сегментов к другой. ^[14]

Если все веса ребер неориентированного графа положительны , то минимаксные расстояния между парами точек (максимальные веса ребер минимаксных путей) образуют ультраметрику ; и наоборот, каждое конечное ультраметрическое пространство возникает таким образом из минимаксных расстояний. ^[15] Структура данных, построенная на основе минимального связующего дерева, позволяет запрашивать минимаксное расстояние между любой парой вершин за постоянное время для каждого запроса, используя наименьшего общего предка запросы в декартовом дереве . Корень декартова дерева представляет собой самое тяжелое минимальное остовное дерево, а дочерние элементы корня — это декартовы деревья, рекурсивно построенные из поддеревьев минимального остовного дерева, образованных путем удаления самого тяжелого ребра. Листья декартова дерева представляют собой вершины входного графа, а минимаксное расстояние между двумя вершинами равно весу узла декартова дерева, который является их наименьшим общим предком. После того, как минимальные ребра остовного дерева отсортированы, это декартово дерево можно построить за линейное время. ^[16]

Ориентированные графы

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

Все пары

Проблема наибольшего широкого пути для всех пар находит применение в методе Шульце для выбора победителя на многосторонних выборах , на которых избиратели ранжируют кандидатов в порядке предпочтения . Метод Шульце строит полный ориентированный граф , вершины которого представляют кандидатов, а каждые две вершины соединены ребром. Каждое ребро направлено от победителя к проигравшему в парном состязании между двумя кандидатами, которых оно соединяет, и помечено перевесом на победу в этом состязании. Затем метод вычисляет самые широкие пути между всеми парами вершин, и победителем становится кандидат, вершина которого имеет более широкие пути к каждому противнику, чем наоборот. ^[3] Результаты выборов с использованием этого метода согласуются с методом Кондорсе — кандидат, который выигрывает все парные соревнования, автоматически побеждает на всех выборах — но обычно он позволяет выбрать победителя даже в тех ситуациях, когда сам метод Кондорсе не дает результатов. ^[17] Метод Шульце использовался несколькими организациями, включая Фонд Викимедиа . ^[18]

Чтобы вычислить максимальную ширину пути для всех пар узлов в плотном ориентированном графе, например тех, которые возникают в приложении для голосования, асимптотически самый быстрый из известных подходов требует времени $O (n (3+ω)/2),$ где ω — показатель степени быстрого умножения матриц . Используя самые известные алгоритмы умножения матриц, эта временная граница становится $O (n 2.688)$ . ^[19] Вместо этого эталонная реализация метода Шульце использует модифицированную версию более простого алгоритма Флойда-Уоршалла , который принимает $O (n 3)$ время. ^[3] Для разреженных графов может оказаться более эффективным многократное применение алгоритма наибольшего пути с одним источником.

Единый источник

Если ребра отсортированы по их весам, то модифицированная версия алгоритма Дейкстры может вычислить узкие места между назначенной начальной вершиной и любой другой вершиной графа за линейное время. Ключевая идея ускорения по сравнению с традиционной версией алгоритма Дейкстры заключается в том, что последовательность расстояний узких мест до каждой вершины в том порядке, в котором вершины рассматриваются этим алгоритмом, представляет собой монотонную подпоследовательность отсортированной последовательности весов ребер; следовательно, очередь приоритетов алгоритма Дейкстры может быть реализована как очередь сегментов : массив, индексированный числами от 1 до $m$ (количество ребер в графе), где ячейка массива $i$ содержит вершины, расстояние до узкого места которых равно весу ребро с позицией $i$ в отсортированном порядке. Этот метод позволяет решить проблему самого широкого пути так же быстро, как и сортировку ; например, если веса ребер представлены в виде целых чисел, то ограничения по времени для целочисленной сортировки списка из $m$ целых чисел будут применимы и к этой задаче. ^[13]

Один источник и один пункт назначения

Берман и Хэндлер (1987) предполагают, что служебные машины и машины скорой помощи должны использовать минимаксные маршруты при возвращении из сервисного вызова на свою базу. В этом приложении время возврата менее важно, чем время ответа, если произойдет еще один вызов службы поддержки, пока автомобиль находится в процессе возврата. Используя минимаксный путь, где вес ребра равен максимальному времени прохождения от точки на ребре до самого дальнего возможного вызова службы поддержки, можно спланировать маршрут, который минимизирует максимально возможную задержку между получением вызова службы и прибытием вызова службы поддержки. ответный автомобиль. ^[7] Улла, Ли и Хассун (2009) используют максиминные пути для моделирования доминирующих цепей реакций в метаболических сетях ; в их модели вес ребра — это свободная энергия метаболической реакции, представленная ребром. ^[5]

Другое применение широчайших путей возникает в алгоритме Форда – Фулкерсона для задачи максимального потока . Многократное увеличение потока по пути максимальной пропускной способности в остаточной сети потока приводит к небольшому ограничению $O (m log U)$ количества увеличений, необходимых для нахождения максимального потока; здесь предполагается, что пропускные способности ребер являются целыми числами, не превышающими $U$ . Однако этот анализ не зависит от поиска пути с точной максимальной пропускной способностью; достаточно любого пути, пропускная способность которого находится в пределах постоянного коэффициента максимума. Объединение этой идеи аппроксимации с методом увеличения кратчайшего пути алгоритма Эдмондса-Карпа приводит к алгоритму максимального потока со временем работы $O (mn log U)$ . ^[6]

Можно очень эффективно находить пути максимальной емкости и минимаксные пути с одним источником и одним пунктом назначения даже в моделях вычислений, которые позволяют только сравнивать веса ребер входного графа, а не выполнять арифметические действия над ними. ^[13]^[20] Алгоритм поддерживает набор $S$ ребер, которые, как известно, содержат ребро узкого места оптимального пути; изначально $S$ — это просто набор всех $m$ ребер графа. На каждой итерации алгоритма он разбивает $S$ на упорядоченную последовательность подмножеств $S 1, S 2, ...$ примерно одинакового размера; количество подмножеств в этом разделе выбирается таким образом, чтобы все точки разделения между подмножествами можно было найти путем повторного поиска медианы за время $O (m)$ . Затем алгоритм повторно взвешивает каждое ребро графа по индексу подмножества, содержащего это ребро, и использует модифицированный алгоритм Дейкстры для перевзвешенного графа; на основе результатов этого вычисления он может за линейное время определить, какое из подмножеств содержит вес ребра узкого места. Затем он заменяет $S$ подмножеством $Si,$ по его определению, содержит вес узкого места, и начинает следующую итерацию с этим новым набором $S.$ которое , Число подмножеств, на которые $можно разбить S$ , увеличивается экспоненциально с каждым шагом, поэтому количество итераций пропорционально повторного логарифма функция $O (log * n)$ , а общее время равно $O (m log * n)$ . ^[20] В модели вычислений, где вес каждого ребра является машинным целым числом, использование повторяющегося деления пополам в этом алгоритме можно заменить методом разделения списков Хана и Торапа (2002) , позволяющим $S$ разбить $на O (\sqrt m).$ меньшие наборы $S i$ за один шаг, что приводит к линейному общему ограничению времени. ^[21]

Евклидовы множества точек

Вариант минимаксной задачи о пути рассматривался также для множества точек евклидовой плоскости . Как и в задаче о неориентированном графе, эту задачу о евклидовом минимаксном пути можно эффективно решить, найдя евклидово минимальное остовное дерево : каждый путь в дереве является минимаксным путем. Однако проблема усложняется, когда требуется путь, который не только минимизирует длину перехода, но также, среди путей с одинаковой длиной перехода, минимизирует или приблизительно минимизирует общую длину пути. Решение можно аппроксимировать с помощью геометрических гаечных ключей . ^[22]

В теории чисел нерешенная проблема гауссовского рва спрашивает, имеют ли минимаксные пути в гауссовских простых числах ограниченную или неограниченную минимаксную длину. То есть существует ли константа $B$ такая, что для каждой пары точек $p$ и $q$ в бесконечном евклидовом множестве точек, определенном гауссовскими простыми числами, минимаксный путь в гауссовских простых числах между $p$ и $q$ имеет минимаксную длину ребра не более $B$ ? ^[23]

Ссылки

^ Поллак, Морис (1960), «Максимальная пропускная способность сети», Operations Research , 8 (5): 733–736, doi : 10.1287/opre.8.5.733 , JSTOR 167387
^ Шачам, Н. (1992), «Многоадресная маршрутизация иерархических данных», Международная конференция IEEE по коммуникациям (ICC '92) , том. 3, стр. 1217–1221, doi : 10.1109/ICC.1992.268047 , hdl : 2060/19990017646 , ISBN 978-0-7803-0599-1 , S2CID 60475077 ; Ван, Чжэн; Кроукрофт, Дж. (1995), «Алгоритмы маршрутизации на основе задержки полосы пропускания», Глобальная конференция по телекоммуникациям IEEE (GLOBECOM '95) , том. 3, стр. 2129–2133, номер документа : 10.1109/GLOCOM.1995.502780 , ISBN. 978-0-7803-2509-8 , S2CID 9117583
^ Jump up to: ^а ^б ^с Шульце, Маркус (2011), «Новый монотонный, независимый от клонов, обратно-симметричный и последовательный по Кондорсе метод выборов с одним победителем», Social Choice and Welfare , 36 (2): 267–303, doi : 10.1007/s00355- 010-0475-4 , S2CID 1927244
^ Jump up to: ^а ^б Фернандес, Елена ; Гарфинкель, Роберт; Арбиол, Роман (1998), «Составление мозаики аэрофотографических карт через швы, определяемые кратчайшими путями узких мест», Operations Research , 46 (3): 293–304, doi : 10.1287/opre.46.3.293 , JSTOR 222823
^ Jump up to: ^а ^б Улла, Э.; Ли, Кёнбум; Хассун, С. (2009), «Алгоритм определения доминирующих метаболических путей», Международная конференция IEEE / ACM по компьютерному проектированию (ICCAD 2009) , стр. 144–150.
^ Jump up to: ^а ^б Ахуджа, Равиндра К .; Маньянти, Томас Л .; Орлин, Джеймс Б. (1993), «Алгоритм масштабирования мощности 7.3», Сетевые потоки: теория, алгоритмы и приложения , Прентис Холл, стр. 210–212, ISBN 978-0-13-617549-0
^ Jump up to: ^а ^б Берман, Одед; Хэндлер, Габриэль Ю. (1987), «Оптимальный минимаксный путь одной сервисной единицы в сети к необслуживаемым пунктам назначения», Transportation Science , 21 (2): 115–122, doi : 10.1287/trsc.21.2.115
^ Ху, TC (1961), «Проблема маршрута максимальной пропускной способности», Operations Research , 9 (6): 898–900, doi : 10.1287/opre.9.6.898 , JSTOR 167055
^ Jump up to: ^а ^б Паннен, Абрахам П. (1991), «Алгоритм с линейным временем для задачи пути максимальной мощности», European Journal of Operational Research , 53 (3): 402–404, doi : 10.1016/0377-2217(91)90073-5
^ Мальпани, Навнеет; Чен, Цзянер (2002), «Заметки о практическом построении путей с максимальной пропускной способностью», Information Processing Letters , 83 (3): 175–180, doi : 10.1016/S0020-0190(01)00323-4 , MR 1904226
^ Шапира, Асаф; Юстер, Рафаэль; Цвик, Ури (2011), «Пути с узкими местами для всех пар во взвешенных по вершинам графах», Algorithmica , 59 (4): 621–633, doi : 10.1007/s00453-009-9328-x , MR 2771114 ; см. п. 4.1, с. 630
^ Камерини, П.М. (1978), «Проблема связующего дерева мин-макс и некоторые расширения», Information Processing Letters , 7 (1): 10–14, doi : 10.1016/0020-0190(78)90030-3
^ Jump up to: ^а ^б ^с Кайбель, Волкер; Пейнхардт, Матиас А.Ф. (2006), О проблеме кратчайшего пути (PDF) , Отчет ZIB 06-22, Центр информационных технологий Конрада Цузе, Берлин
^ Альт, Хельмут ; Годау, Майкл (1995), «Вычисление расстояния Фреше между двумя многоугольными кривыми» (PDF) , Международный журнал вычислительной геометрии и приложений , 5 (1–2): 75–91, doi : 10.1142/S0218195995000064 .
^ Леклерк, Бруно (1981), «Комбинаторное описание ультраметрики», Центр социальной математики. Практическая школа повышения квалификации. Математика и гуманитарные науки (на французском языке) (73): 5–37, 127, MR 0623034
^ Демейн, Эрик Д .; Ландау, Гад М .; Вейманн, Орен (2009), «О декартовых деревьях и запросах минимума диапазона», Автоматы, языки и программирование, 36-й международный коллоквиум, ICALP 2009, Родос, Греция, 5–12 июля 2009 г. , Конспекты лекций по информатике, том. 5555, стр. 341–353, doi : 10.1007/978-3-642-02927-1_29 , hdl : 1721.1/61963 , ISBN 978-3-642-02926-4
^ Более конкретно, единственный вид связи, который метод Шульце не может разорвать, - это между двумя кандидатами, у которых одинаково широкие пути друг к другу.
^ См. Джесси Пламондон-Уиллард, Выборы в Совет директоров с использованием преференциального голосования , май 2008 г.; Марк Райан, результаты выборов в Совет Викимедиа 2008 г. , июнь 2008 г.; Выборы в совет директоров 2008 г. , июнь 2008 г.; и выборы в совет директоров 2009 г. , август 2009 г.
^ Дуан, Ран; Петти, Сет (2009), «Быстрые алгоритмы умножения (макс, мин)-матриц и кратчайшие пути с узкими местами», Труды 20-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '09) , стр. 384–391 . Информацию о более раннем алгоритме, который также использовал быстрое умножение матриц для ускорения самых широких путей всех пар, см. Василевска, Вирджиния ; Уильямс, Райан ; Юстер, Рафаэль (2007), «Пути с узкими местами для всех пар для общих графов в истинно субкубическом времени», Труды 39-го ежегодного симпозиума ACM по теории вычислений (STOC '07) , Нью-Йорк: ACM, стр. 585– 589, CiteSeerX 10.1.1.164.9808 , doi : 10.1145/1250790.1250876 , ISBN 9781595936318 , MR 2402484 , S2CID 9353065 и глава 5 Василевска, Вирджиния (2008), Эффективные алгоритмы для решения задач пути во взвешенных графах (PDF) , доктор философии. диссертация, отчет CMU-CS-08-147, Школа компьютерных наук Университета Карнеги-Меллона
^ Jump up to: ^а ^б Габоу, Гарольд Н .; Тарьян, Роберт Э. (1988), «Алгоритмы для решения двух узких задач оптимизации» , Журнал алгоритмов , 9 (3): 411–417, doi : 10.1016/0196-6774(88)90031-4 , MR 0955149
^ Хан, Ицзе; Торуп, М. (2002), «Целочисленная сортировка в $ожидаемом времени O (n \sqrt log log n)$ и линейном пространстве», Proc. 43-й ежегодный симпозиум по основам информатики (FOCS 2002) , стр. 135–144, doi : 10.1109/SFCS.2002.1181890 , ISBN 978-0-7695-1822-0 , S2CID 5245628 .
^ Бозе, Просенджит ; Махешвари, Анил; Нарасимхан, Гири; Смид, Мишель; Зе, Норберт (2004), «Аппроксимация кратчайших путей с узкими местами в геометрической форме», Вычислительная геометрия. Теория и приложения , 29 (3): 233–249, doi : 10.1016/j.comgeo.2004.04.003 , MR 2095376.
^ Гетнер, Эллен; Вагон, Стэн ; Уик, Брайан (1998), «Прогулка по простым числам Гаусса», American Mathematical Monthly , 105 (4): 327–337, doi : 10.2307/2589708 , JSTOR 2589708 , MR 1614871 .

[1] Поллак, Морис (1960), «Максимальная пропускная способность сети», Operations Research , 8 (5): 733–736, doi : 10.1287/opre.8.5.733 , JSTOR 167387

[2] Шачам, Н. (1992), «Многоадресная маршрутизация иерархических данных», Международная конференция IEEE по коммуникациям (ICC '92) , том. 3, стр. 1217–1221, doi : 10.1109/ICC.1992.268047 , hdl : 2060/19990017646 , ISBN 978-0-7803-0599-1 , S2CID 60475077 ; Ван, Чжэн; Кроукрофт, Дж. (1995), «Алгоритмы маршрутизации на основе задержки полосы пропускания», Глобальная конференция по телекоммуникациям IEEE (GLOBECOM '95) , том. 3, стр. 2129–2133, номер документа : 10.1109/GLOCOM.1995.502780 , ISBN. 978-0-7803-2509-8 , S2CID 9117583

[Schulze-3] Jump up to: ^а ^б ^с Шульце, Маркус (2011), «Новый монотонный, независимый от клонов, обратно-симметричный и последовательный по Кондорсе метод выборов с одним победителем», Social Choice and Welfare , 36 (2): 267–303, doi : 10.1007/s00355- 010-0475-4 , S2CID 1927244

[fga-4] Jump up to: ^а ^б Фернандес, Елена ; Гарфинкель, Роберт; Арбиол, Роман (1998), «Составление мозаики аэрофотографических карт через швы, определяемые кратчайшими путями узких мест», Operations Research , 46 (3): 293–304, doi : 10.1287/opre.46.3.293 , JSTOR 222823

[ulh09-5] Jump up to: ^а ^б Улла, Э.; Ли, Кёнбум; Хассун, С. (2009), «Алгоритм определения доминирующих метаболических путей», Международная конференция IEEE / ACM по компьютерному проектированию (ICCAD 2009) , стр. 144–150.

[amo-6] Jump up to: ^а ^б Ахуджа, Равиндра К .; Маньянти, Томас Л .; Орлин, Джеймс Б. (1993), «Алгоритм масштабирования мощности 7.3», Сетевые потоки: теория, алгоритмы и приложения , Прентис Холл, стр. 210–212, ISBN 978-0-13-617549-0

[bh87-7] Jump up to: ^а ^б Берман, Одед; Хэндлер, Габриэль Ю. (1987), «Оптимальный минимаксный путь одной сервисной единицы в сети к необслуживаемым пунктам назначения», Transportation Science , 21 (2): 115–122, doi : 10.1287/trsc.21.2.115

[8] Ху, TC (1961), «Проблема маршрута максимальной пропускной способности», Operations Research , 9 (6): 898–900, doi : 10.1287/opre.9.6.898 , JSTOR 167055

[punnen-9] Jump up to: ^а ^б Паннен, Абрахам П. (1991), «Алгоритм с линейным временем для задачи пути максимальной мощности», European Journal of Operational Research , 53 (3): 402–404, doi : 10.1016/0377-2217(91)90073-5

[10] Мальпани, Навнеет; Чен, Цзянер (2002), «Заметки о практическом построении путей с максимальной пропускной способностью», Information Processing Letters , 83 (3): 175–180, doi : 10.1016/S0020-0190(01)00323-4 , MR 1904226

[11] Шапира, Асаф; Юстер, Рафаэль; Цвик, Ури (2011), «Пути с узкими местами для всех пар во взвешенных по вершинам графах», Algorithmica , 59 (4): 621–633, doi : 10.1007/s00453-009-9328-x , MR 2771114 ; см. п. 4.1, с. 630

[12] Камерини, П.М. (1978), «Проблема связующего дерева мин-макс и некоторые расширения», Information Processing Letters , 7 (1): 10–14, doi : 10.1016/0020-0190(78)90030-3

[kp-13] Jump up to: ^а ^б ^с Кайбель, Волкер; Пейнхардт, Матиас А.Ф. (2006), О проблеме кратчайшего пути (PDF) , Отчет ZIB 06-22, Центр информационных технологий Конрада Цузе, Берлин

[14] Альт, Хельмут ; Годау, Майкл (1995), «Вычисление расстояния Фреше между двумя многоугольными кривыми» (PDF) , Международный журнал вычислительной геометрии и приложений , 5 (1–2): 75–91, doi : 10.1142/S0218195995000064 .

[15] Леклерк, Бруно (1981), «Комбинаторное описание ультраметрики», Центр социальной математики. Практическая школа повышения квалификации. Математика и гуманитарные науки (на французском языке) (73): 5–37, 127, MR 0623034

[16] Демейн, Эрик Д .; Ландау, Гад М .; Вейманн, Орен (2009), «О декартовых деревьях и запросах минимума диапазона», Автоматы, языки и программирование, 36-й международный коллоквиум, ICALP 2009, Родос, Греция, 5–12 июля 2009 г. , Конспекты лекций по информатике, том. 5555, стр. 341–353, doi : 10.1007/978-3-642-02927-1_29 , hdl : 1721.1/61963 , ISBN 978-3-642-02926-4

[17] Более конкретно, единственный вид связи, который метод Шульце не может разорвать, - это между двумя кандидатами, у которых одинаково широкие пути друг к другу.

[Wikimedia-18] См. Джесси Пламондон-Уиллард, Выборы в Совет директоров с использованием преференциального голосования , май 2008 г.; Марк Райан, результаты выборов в Совет Викимедиа 2008 г. , июнь 2008 г.; Выборы в совет директоров 2008 г. , июнь 2008 г.; и выборы в совет директоров 2009 г. , август 2009 г.

[19] Дуан, Ран; Петти, Сет (2009), «Быстрые алгоритмы умножения (макс, мин)-матриц и кратчайшие пути с узкими местами», Труды 20-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '09) , стр. 384–391 . Информацию о более раннем алгоритме, который также использовал быстрое умножение матриц для ускорения самых широких путей всех пар, см. Василевска, Вирджиния ; Уильямс, Райан ; Юстер, Рафаэль (2007), «Пути с узкими местами для всех пар для общих графов в истинно субкубическом времени», Труды 39-го ежегодного симпозиума ACM по теории вычислений (STOC '07) , Нью-Йорк: ACM, стр. 585– 589, CiteSeerX 10.1.1.164.9808 , doi : 10.1145/1250790.1250876 , ISBN 9781595936318 , MR 2402484 , S2CID 9353065 и глава 5 Василевска, Вирджиния (2008), Эффективные алгоритмы для решения задач пути во взвешенных графах (PDF) , доктор философии. диссертация, отчет CMU-CS-08-147, Школа компьютерных наук Университета Карнеги-Меллона

[gt-20] Jump up to: ^а ^б Габоу, Гарольд Н .; Тарьян, Роберт Э. (1988), «Алгоритмы для решения двух узких задач оптимизации» , Журнал алгоритмов , 9 (3): 411–417, doi : 10.1016/0196-6774(88)90031-4 , MR 0955149

[21] Хан, Ицзе; Торуп, М. (2002), «Целочисленная сортировка в $ожидаемом времени O (n \sqrt log log n)$ и линейном пространстве», Proc. 43-й ежегодный симпозиум по основам информатики (FOCS 2002) , стр. 135–144, doi : 10.1109/SFCS.2002.1181890 , ISBN 978-0-7695-1822-0 , S2CID 5245628 .

[22] Бозе, Просенджит ; Махешвари, Анил; Нарасимхан, Гири; Смид, Мишель; Зе, Норберт (2004), «Аппроксимация кратчайших путей с узкими местами в геометрической форме», Вычислительная геометрия. Теория и приложения , 29 (3): 233–249, doi : 10.1016/j.comgeo.2004.04.003 , MR 2095376.

[23] Гетнер, Эллен; Вагон, Стэн ; Уик, Брайан (1998), «Прогулка по простым числам Гаусса», American Mathematical Monthly , 105 (4): 327–337, doi : 10.2307/2589708 , JSTOR 2589708 , MR 1614871 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]