Набор дуг обратной связи

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

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

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

Приложения

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

В спортивных соревнованиях с круговой системой результаты каждой игры могут быть записаны путем направления преимущества от проигравшего к победителю каждой игры. Нахождение минимальной дуги обратной связи в полученном графе, изменение ее ребер и топологическое упорядочение дают рейтинг всем конкурентам. Среди всех различных способов выбора рейтинга он сводит к минимуму общее количество неудач, игр, в которых участник с более низким рейтингом побеждает конкурента с более высоким рейтингом. ^[2]^[3]^[4] Во многих видах спорта используются более простые методы построения рейтинговых систем групповых турниров, основанные на очках, начисляемых за каждую игру; ^[5] эти методы могут обеспечить постоянное приближение к рейтингу минимального отклонения. ^[6]
В приматологии в этологии и, в более общем плане , иерархии доминирования часто определяются путем поиска порядка с наименьшим количеством изменений в наблюдаемом поведении доминирования, что является еще одной формой проблемы множества дуг минимальной обратной связи. ^[7]^[8]^[9]
В математической психологии представляет интерес определение ранжирования субъектами наборов объектов в соответствии с заданным критерием, например, их предпочтением или восприятием размера, на основе попарных сравнений между всеми парами объектов. Минимальная дуга обратной связи, установленная в турнирном графике, обеспечивает рейтинг, который не согласуется с как можно меньшим количеством парных результатов. ^[2]^[10] В качестве альтернативы, если эти сравнения приводят к независимым вероятностям для каждого парного упорядочения, то оценка максимального правдоподобия общего рейтинга может быть получена путем преобразования этих вероятностей в логарифмические вероятности и нахождения дуги обратной связи с минимальным весом, установленной в результирующем турнире. ^[2]^[3]
Тот же порядок максимального правдоподобия можно использовать для сериализации , проблемы в статистике и исследовательском анализе данных , заключающейся в упорядочивании элементов в линейном порядке, в тех случаях, когда доступны данные, обеспечивающие попарное сравнение между элементами. ^[3]^[11]^[12]
При ранжированном голосовании метод Кемени -Янга можно описать как поиск порядка, который минимизирует сумму по парам кандидатов числа избирателей, которые предпочитают противоположный порядок для этой пары. ^[13] Это можно сформулировать и решить как задачу множества дуг обратной связи с минимальным весом, в которой вершины представляют кандидатов, ребра направлены так, чтобы представлять победителя каждого личного соревнования, а стоимость каждого ребра представляет количество избирателей. который был бы недоволен, если бы присвоил более высокий рейтинг проигравшему в очном противостоянии. ^[14]

Еще одно раннее применение наборов дуг обратной связи касалось проектирования последовательных логических схем, в которых сигналы могут циклически распространяться по схеме, а не всегда переходить от входов к выходам. В таких схемах минимальный набор дуг обратной связи характеризует количество точек, в которых необходимо усиление, чтобы позволить сигналам распространяться без потери информации. ^[15] В синхронных схемах, состоящих из асинхронных компонентов, синхронизация может быть достигнута путем размещения тактовых вентилей на краях набора дуг обратной связи. ^[16] Кроме того, разрезание цепи на наборе дуг обратной связи сводит оставшуюся схему к комбинационной логике , упрощая ее анализ, а размер набора дуг обратной связи определяет, какой объем дополнительного анализа необходим для понимания поведения цепи на разрезе. ^[15] Аналогичным образом, в схемах технологических химического машиностроения разрыв границ технологической диаграммы на наборе дуг обратной связи и угадывание или проверка всех возможностей значений на этих краях позволяет систематически анализировать остальную часть процесса, поскольку его ацикличность. В этом приложении идея ломать края таким образом называется «разрывом». ^[17]

При рисовании многослойного графа вершины данного ориентированного графа разбиваются на упорядоченную последовательность подмножеств (слоев рисунка), и каждое подмножество размещается вдоль горизонтальной линии этого рисунка, причем ребра проходят вверх и вниз между ними. слои. В чертежах этого типа желательно, чтобы большинство или все ребра были ориентированы последовательно вниз, а не смешивались с ребрами, направленными вверх и вниз, чтобы отношения достижимости на чертеже были более визуально очевидными. Это достигается путем нахождения минимального или минимального набора дуг обратной связи, изменения ребер в этом наборе местами, а затем выбора разделения на слои таким образом, чтобы это соответствовало топологическому порядку результирующего ациклического графа. ^[18]^[19] Наборы дуг обратной связи также использовались для другой подзадачи рисования многослойных графов - упорядочивания вершин в последовательных парах слоев. ^[20]

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

Алгоритмы

Эквиваленты

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

Набор дуг обратной связи данного графа $G$ то же самое, что набор вершин обратной связи ориентированного линейного графа $G$ . Здесь набор вершин обратной связи определяется аналогично набору дуг обратной связи как подмножество вершин графа, удаление которых приведет к устранению всех циклов. Линейный график ориентированного графа $G$ имеет вершину для каждого ребра $G$ и ребро для каждого двуреберного пути в $G$ . В другом направлении минимальный набор вершин обратной связи данного графа $G$ может быть получено из решения задачи о минимальном наборе дуг обратной связи на графе, полученном путем разделения каждой вершины $G$ на две вершины: одну для входящих ребер и одну для исходящих ребер. Эти преобразования позволяют преобразовывать друг в друга точные алгоритмы для наборов дуг обратной связи и наборов вершин обратной связи с соответствующим переводом границ их сложности. Однако это преобразование не сохраняет качество аппроксимации задачи о максимальном ациклическом подграфе. ^[21]^[24]

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

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

Точный

Один из способов найти минимальный набор дуг обратной связи - это найти такой порядок вершин, чтобы как можно меньше ребер было направлено от более поздних вершин к более ранним в упорядочении. ^[27] Поиск перестановок всех $n$ -граф вершин займет время $O(n!)$ , но метод динамического программирования , основанный на алгоритме Хелда – Карпа, позволяет найти оптимальную перестановку за время $O(n2^{n})$ , также используя экспоненциальное количество пространства. ^[28]^[29] Алгоритм «разделяй и властвуй» , который проверяет все разбиения вершин на два равных подмножества и выполняет рекурсию внутри каждого подмножества, может решить проблему вовремя . $O(4^{n}/{\sqrt {n}})$ , используя полиномиальное пространство . ^[29]

В параметризованной сложности время работы алгоритмов измеряется не только размером входного графа, но и отдельным параметром графа. В частности, для задачи о минимальном наборе дуг обратной связи так называемым естественным параметром является размер минимального набора дуг обратной связи. На графиках с $n$ вершины с натуральным параметром $k$ , проблема набора дуг обратной связи может быть решена вовремя $O(n^{4}4^{k}k^{3}k!)$ , преобразуя ее в эквивалентную задачу набора вершин обратной связи и применяя параметризованный алгоритм набора вершин обратной связи. Поскольку показатель степени $n$ в этом алгоритме является константой $4$ , независимо от $k$ , этот алгоритм называется управляемым с фиксированными параметрами. ^[30]

Другие параметры, помимо естественного параметра, также были изучены. Управляемый алгоритм с фиксированными параметрами, использующий динамическое программирование, может вовремя найти минимальные наборы дуг обратной связи . $O(2^{r}m^{4}\log m)$ , где $r$ — ранг схемы базового неориентированного графа. Ранг схемы — это неориентированный аналог множества дуг обратной связи, минимальное количество ребер, которые необходимо удалить из графа, чтобы свести его к остовному дереву ; его гораздо проще вычислить, чем набор минимальных дуг обратной связи. ^[24] Для графиков ширины дерева $t$ Динамическое программирование на древовидной декомпозиции графа может найти минимальную дугу обратной связи, установленную за время, полиномиальное по размеру графа и экспоненциальное по времени. $O(t\log t)$ . Согласно гипотезе экспоненциального времени , нет лучшей зависимости от $t$ возможно. ^[31]

Вместо минимизации размера набора дуг обратной связи исследователи также рассмотрели возможность минимизировать максимальное количество ребер, удаленных из любой вершины. Этот вариант задачи может быть решен за линейное время . ^[32] Все наборы минимальных дуг обратной связи могут быть перечислены с помощью алгоритма с полиномиальной задержкой на набор. ^[33]

Приблизительный

Нерешенная задача по математике :

Имеет ли задача набора дуг обратной связи алгоритм аппроксимации с постоянным коэффициентом аппроксимации?

(еще нерешенные задачи по математике)

Самый известный алгоритм аппроксимации с полиномиальным временем для набора дуг обратной связи имеет непостоянный коэффициент аппроксимации. $O(\log n\log \log n)$ . Это означает, что размер набора дуг обратной связи, который он обнаруживает, не более чем в один раз превышает оптимальный. ^[21] Определение того, имеет ли набор дуг обратной связи алгоритм аппроксимации с постоянным соотношением или необходимо непостоянное соотношение, остается открытой проблемой. ^[34]

Задача о максимальном ациклическом подграфе имеет простой алгоритм аппроксимации, который обеспечивает коэффициент аппроксимации ${\tfrac {1}{2}}$ :

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

Это можно улучшить, используя жадный алгоритм выбора порядка. Этот алгоритм находит и удаляет вершину, у которой количество входящих и исходящих ребер находится как можно дальше друг от друга, рекурсивно упорядочивает оставшийся граф, а затем помещает удаленную вершину в один конец полученного порядка. Для графиков с $m$ края и $n$ вершин, это создает ациклический подграф с $m/2+n/6$ края за линейное время, что дает коэффициент аппроксимации ${\tfrac {1}{2}}+\Omega (n/m)$ . ^[35] Другой, более сложный алгоритм аппроксимации полиномиальным временем применяется к графам с максимальной степенью $\Delta$ и находит ациклический подграф с $m/2+\Omega (m/{\sqrt {\Delta }})$ ребра, что дает коэффициент аппроксимации вида ${\tfrac {1}{2}}+\Omega (1/{\sqrt {\Delta }})$ . ^[36]^[37] Когда $\Delta =3$ , коэффициент аппроксимации $8/9$ может быть достигнуто. ^[38]

Ограниченные входы

В ориентированных плоских графах проблема множества дуг обратной связи двойственна проблеме сжатия набора ребер (дисоединения ) , чтобы сделать результирующий граф сильно связным . ^[39] Эта двойственная задача полиномиально разрешима: ^[40] и, следовательно, проблема набора плоских дуг с минимальной обратной связью также является проблемой. ^[41]^[40] Это можно решить со временем $O(n^{5/2}\log n)$ . ^[42] Взвешенный вариант проблемы можно решить вовремя $O(n^{3})$ , ^[39] или когда веса представляют собой положительные целые числа, которые не превышают числа $N$ , во времени $O(n^{5/2}\log nN)$ . ^[42] Эти планарные алгоритмы можно распространить на графы, не имеющие графа полезности. $K_{3,3}$ в качестве минора графа , используя тот факт, что трехсвязные компоненты этих графов либо плоские, либо имеют ограниченный размер. ^[26] Плоские графы также были обобщены другим способом на класс ориентированных графов, называемых слабо ациклическими орграфами , определяемыми целостностью определенного многогранника, связанного с их наборами дуг обратной связи . Каждый планарный ориентированный граф является слабо ациклическим в этом смысле, и проблема множества дуг обратной связи может быть решена за полиномиальное время для всех слабо ациклических орграфов. ^[43]

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

Когда проблема набора дуг с минимальной обратной связью ограничивается турнирами , она имеет схему аппроксимации с полиномиальным временем , которая обобщается до взвешенной версии проблемы. ^[45] Известен также субэкспоненциальный параметризованный алгоритм для взвешенных наборов дуг обратной связи на турнирах. ^[14] Задача о максимальном ациклическом подграфе для плотных графов также имеет схему аппроксимации за полиномиальное время. Его основные идеи заключаются в том, чтобы применить рандомизированное округление к линейного программирования релаксации задачи и дерандомизировать полученный алгоритм с помощью обходов по расширительным графам . ^[34]^[46]

Твердость

NP-твердость

Чтобы применить теорию NP-полноты к минимальному набору дуг обратной связи, необходимо изменить проблему с задачи оптимизации (сколько ребер можно удалить, чтобы прервать все циклы) на эквивалентную версию решения с ответом «да» или нет ответа (можно ли удалить $k$ края). Таким образом, вариант решения задачи множества дуг обратной связи принимает в качестве входных данных как ориентированный граф, так и число. $k$ . Он спрашивает, можно ли разорвать все циклы, удалив не более $k$ ребра или, что то же самое, существует ли ациклический подграф с хотя бы $|E(G)|-k$ края. Эта задача является NP-полной , а это означает, что ни она, ни задача оптимизации не должны иметь алгоритмы с полиномиальным временем. Это была одна из Ричарда М. Карпа первоначальных 21 NP-полных задач ; его NP-полнота была доказана Карпом и Юджином Лоулером , показав, что входные данные для другой сложной проблемы, проблемы вершинного покрытия , могут быть преобразованы («сокращены») в эквивалентные входные данные для задачи решения множества дуг обратной связи. ^[47]^[48]

Некоторые NP-полные задачи могут стать проще, если их входные данные ограничены особыми случаями. Но для самого важного частного случая задачи о множестве дуг обратной связи, а именно турниров, проблема остается NP-полной. ^[49]^[50]

Неприближаемость

Класс сложности APX определяется как состоящий из задач оптимизации, которые имеют алгоритм аппроксимации с полиномиальным временем, обеспечивающий постоянный коэффициент аппроксимации . Хотя такие аппроксимации для задачи набора дуг обратной связи неизвестны, известно, что проблема APX-сложна , а это означает, что точные аппроксимации для нее можно использовать для достижения столь же точных аппроксимаций для всех других задач в APX. В результате доказательства твердости, если только P = NP , он не имеет коэффициента аппроксимации полиномиального времени лучше, чем 1,3606. Это тот же порог жесткости аппроксимации, который известен для вершинного покрытия, и в доказательстве используется редукция Карпа – Лоулера от вершинного покрытия к набору дуг обратной связи, что сохраняет качество аппроксимации. ^[34]^[51]^[52]^[53] Другими словами, проблема максимального ациклического подграфа также является APX-трудной и NP-трудной для аппроксимации с точностью до коэффициента 65/66 от оптимального. ^[38]

Трудность аппроксимации этих задач также изучалась при недоказанных предположениях о вычислительной сложности , которые являются стандартными в теории сложности вычислений, но более сильными, чем P ≠ NP. Если гипотеза об уникальных играх верна, то задачу о наборе минимальных дуг обратной связи трудно аппроксимировать за полиномиальное время с точностью до любого постоянного множителя, а задачу о множестве дуг о максимальной обратной связи трудно аппроксимировать с точностью до коэффициента ${\tfrac {1}{2}}+\varepsilon$ , для каждого $\varepsilon >0$ . ^[54] За пределами полиномиального времени для алгоритмов аппроксимации, если гипотеза экспоненциального времени верна, то для каждого $\varepsilon >0$ минимальный набор дуг обратной связи не имеет аппроксимации в пределах коэффициента ${\tfrac {7}{6}}-\varepsilon$ которое можно вычислить за субэкспоненциальное время $O(2^{n^{1-\varepsilon }})$ . ^[55]

Теория

В плоских ориентированных графах проблема множества дуг обратной связи подчиняется теореме о мин-максе : минимальный размер набора дуг обратной связи равен максимальному количеству направленных циклов, не пересекающихся по ребрам, которые можно найти в графе. ^[41]^[56] Это неверно для некоторых других графиков; например, на первой иллюстрации показана ориентированная версия непланарного графа. $K_{3,3}$ в котором минимальный размер набора дуг обратной связи равен двум, а максимальное количество направленных циклов, не пересекающихся по краям, - только один.

Каждый граф турнира имеет гамильтонов путь , и гамильтоновы пути один к одному соответствуют минимальным наборам дуг обратной связи, не пересекающимся с соответствующим путем. Гамильтонов путь для набора дуг обратной связи находится путем перестановки его дуг и нахождения топологического порядка результирующего ациклического турнира. Каждая последовательная пара порядка должна быть непересекающейся с наборами дуг обратной связи, поскольку в противном случае можно было бы найти меньший набор дуг обратной связи, перевернув эту пару. Следовательно, такое упорядочение дает путь по дугам исходного турнира, охватывающий все вершины. И наоборот, из любого гамильтонова пути набор ребер, соединяющих более поздние вершины пути с более ранними, образует множество дуг обратной связи. Он минимален, поскольку каждое его ребро принадлежит циклу, ребра гамильтоновых путей которого не пересекаются со всеми другими такими циклами. ^[57] В турнире может случиться так, что минимальный набор дуг обратной связи и максимальный ациклический подграф оба находятся близко к половине ребер. Точнее, каждый граф турнира имеет набор дуг обратной связи размером ${\tbinom {n}{2}}/2-\Omega (n^{3/2})$ , а некоторые турниры требуют размера ${\tbinom {n}{2}}/2-O(n^{3/2})$ . ^[58] для Практически всех турниров размер не менее ${\tbinom {n}{2}}/2-1.73n^{3/2}$ . ^[59] Любой ориентированный ациклический граф $D$ может быть встроен как подграф более крупного турнирного графа таким образом, что $D$ это уникальный набор дуг турнира с минимальной обратной связью. Размер этого турнира определяется как «обратное число » $D$ , а среди ориентированных ациклических графов с тем же числом вершин он наибольший, когда $D$ сам по себе является (ациклическим) турниром. ^[60]^[61]

Ориентированный граф имеет эйлеров обход всякий раз, когда он сильно связен и каждая вершина имеет одинаковое количество входящих и исходящих ребер. Для такого графа с $m$ края и $n$ вершин, размер минимального набора дуг обратной связи всегда не менее $(m^{2}+mn)/2n^{2}$ . Существует бесконечно много эйлеровых ориентированных графов, для которых эта оценка точна. ^[62] Если ориентированный граф имеет $n$ вершин, с не более чем тремя ребрами на вершину, то он имеет набор дуг обратной связи не более $n/3$ ребер, а некоторые графы требуют именно столько. Если ориентированный граф имеет $m$ ребер, не более четырех ребер на вершину, то он имеет набор дуг обратной связи не более $m/3$ ребер, а некоторые графы требуют именно столько. ^[63]

Ссылки

^ «Основная сетка – мужчины» , Рио, 2016 г. , Международная федерация волейбола , заархивировано из оригинала 23 декабря 2016 г. , получено 14 ноября 2021 г.
^ Перейти обратно: ^а ^б ^с Хьюберт, Лоуренс (1976), «Сериация с использованием асимметричных мер близости», Британский журнал математической и статистической психологии , 29 (1): 32–52, doi : 10.1111/j.2044-8317.1976.tb00701.x , MR 0429180
^ Перейти обратно: ^а ^б ^с Ремидж, Рассел-младший; Томпсон, Вашингтон-младший (1966), «Рейтинги парных сравнений максимального правдоподобия», Biometrika , 53 (1–2): 143–149, doi : 10.1093/biomet/53.1-2.143 , JSTOR 2334060 , MR 0196854 , PMID 5964054
^ Годдард, Стивен Т. (1983), «Рейтинг в турнирах и групповом принятии решений», Management Science , 29 (12): 1384–1392, doi : 10.1287/mnsc.29.12.1384 , MR 0809110 ; обратите внимание, что алгоритм, предложенный Годдардом для определения рейтингов с минимальным нарушением, неверен.
^ Вазири, Бабак; Дабадгао, Шонак; Да, Юверн; Морин, Томас Л. (январь 2018 г.), «Свойства методов спортивного ранжирования» (PDF) , Журнал Общества операционных исследований , 69 (5): 776–787, doi : 10.1057/s41274-017-0266-8 , S2CID 51887586
^ Копперсмит, Дон ; Флейшер, Лиза К.; Рурда, Атри (2010), «Упорядочение по взвешенному количеству побед дает хороший рейтинг для взвешенных турниров», Транзакции ACM по алгоритмам , 6 (3): A55:1–A55:13, doi : 10.1145/1798596.1798608 , MR 2682624 , S2CID 18416
^ Сейфарт, Роберт М. (ноябрь 1976 г.), «Социальные отношения среди взрослых самок павианов», Animal Behavior , 24 (4): 917–938, doi : 10.1016/s0003-3472(76)80022-x , S2CID 54284406
^ Эстеп, DQ; Кроуэлл-Дэвис, СЛ; Эрл-Костелло, Южная Каролина; Бити, С.А. (январь 1993 г.), «Изменения в социальном поведении кобыл тяжеловозов (Equus caballus), совпадающие с вырождением жеребят», Applied Animal Behavior Science , 35 (3): 199–213, doi : 10.1016/0168-1591(93) 90137-э
^ Эйкворт, Джордж К. (апрель 2019 г.), «Доминирование таракана (науфоэта)», Поведение насекомых , CRC Press, стр. 120–126, doi : 10.1201/9780429049262-18 , S2CID 203898549
^ Слейтер, Патрик (1961), «Несоответствия в графике парных сравнений», Biometrika , 48 (3–4): 303–312, doi : 10.1093/biomet/48.3-4.303 , JSTOR 2332752
^ Бранк, HD (1960), «Математические модели для ранжирования на основе парных сравнений», Журнал Американской статистической ассоциации , 55 (291): 503–520, doi : 10.2307/2281911 , JSTOR 2281911 , MR 0115242 ; опубликовано в предварительной форме как документ ASTIA № AD 206 573, ВВС США, Управление научных исследований, ноябрь 1958 г., hdl : 2027/mdp.39015095254010
^ Томпсон, Вашингтон младший; Ремейдж, Рассел-младший (1964), «Рейтинги на основе парных сравнений», Annals of Mathematical Статистика , 35 (2): 739–747, doi : 10.1214/aoms/1177703572 , JSTOR 2238526 , MR 0161419
^ Кемени, Джон Г. (осень 1959 г.), «Математика без чисел», Дедал , 88 (4): 577–591, JSTOR 20026529
^ Перейти обратно: ^а ^б Карпински, Марек ; Шуди, Уоррен (2010), «Более быстрые алгоритмы для турнира по набору дуг обратной связи, агрегации рангов Кемени и турнира по промежуткам», в Чеонг, Отфрид ; Чва, Кён Ён; Пак, Кунсу (ред.), «Алгоритмы и вычисления – 21-й международный симпозиум», ISAAC 2010, остров Чеджу, Корея, 15–17 декабря 2010 г., Материалы, часть I , конспекты лекций по информатике, том. 6506, Springer, стр. 3–14, arXiv : 1006.4396 , doi : 10.1007/978-3-642-17517-6_3 , S2CID 16512997
^ Перейти обратно: ^а ^б Унгер, Стивен Х. (26 апреля 1957 г.), Исследование асинхронных сетей с логической обратной связью , Технические отчеты, том. 320, Массачусетский технологический институт, Исследовательская лаборатория электроники, hdl : 1721.1/4763
^ Ферер, Джон Р.; Джордан, Гарри Ф. (декабрь 1995 г.), «Размещение часовых вентилей во времяпролетных оптоэлектронных схемах», Applied Optics , 34 (35): 8125–8136, Bibcode : 1995ApOpt..34.8125F , doi : 10.1364/ao .34.008125 , PMID 21068927
^ Розен, Эдвард М.; Хенли, Эрнест Дж. (лето 1968 г.), «Новая стехиометрия» , Chemical Engineering Education , 2 (3): 120–125, заархивировано из оригинала 02 августа 2021 г. , получено 2 августа 2021 г.
^ Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), «Многослойные рисунки орграфов», Рисование графиков: алгоритмы визуализации графов , Прентис Холл , стр. 265–302, ISBN 978-0-13-301615-4
^ Бастерт, Оливер; Матушевский, Кристиан (2001), «Многослойные рисунки орграфов», Кауфманн, Майкл; Вагнер, Доротея (ред.), Рисование графиков: методы и модели , Конспекты лекций по информатике, том. 2025, Springer-Verlag, стр. 87–120, номер документа : 10.1007/3-540-44969-8_5.
^ Деметреску, Камил; Финокки, Ирен (2001), «Разорвите «правильные» циклы и получите «лучший» рисунок», Журнал экспериментальной алгоритмики ACM , 6 : 171–182, MR 2027115.
^ Перейти обратно: ^а ^б ^с Эвен, Г.; Наор, Дж .; Шибер, Б .; Судан, М. (1998), «Аппроксимация наборов минимальной обратной связи и мультиразрезов в ориентированных графах», Algorithmica , 20 (2): 151–174, doi : 10.1007/PL00009191 , MR 1484534 , S2CID 2437790
^ Перейти обратно: ^а ^б Минура, Тошими (1982), «Возвращение к предотвращению тупиков», Journal of the ACM , 29 (4): 1023–1048, doi : 10.1145/322344.322351 , MR 0674256 , S2CID 5284738
^ Мишра, Сунака; Сикдар, Крипасиндху (2004), «Об аппроксимируемости линейного порядка и связанных с ним задачах NP-оптимизации на графах», Discrete Applied Mathematics , 136 (2–3): 249–269, doi : 10.1016/S0166-218X(03)00444- Х , МР 2045215
^ Перейти обратно: ^а ^б Хехт, Майкл (2017), «Точные локализации наборов обратной связи», Теория вычислительных систем , 62 (5): 1048–1084, arXiv : 1702.07612 , doi : 10.1007/s00224-017-9777-6 , S2CID 18394348
^ Парк, С.; Акерс, С.Б. (1992), «Эффективный метод поиска минимального набора дуг обратной связи в ориентированных графах», Труды Международного симпозиума IEEE по схемам и системам 1992 года (ISCAS '92) , том. 4, стр. 1863–1866, номер документа : 10.1109/iscas.1992.230449 , S2CID 122603659 .
^ Перейти обратно: ^а ^б Нутов, Зеев; Пенн, Михал (2000), «О целостности, устойчивости и составе упаковок и покрытий дициклов», Journal of Combinatorial Optimization , 4 (2): 235–251, doi : 10.1023/A:1009802905533 , MR 1772828 , S2CID 207632524
^ Янгер, Д. (1963), «Минимальные наборы дуг обратной связи для ориентированного графа», IEEE Transactions on Circuit Theory , 10 (2): 238–245, doi : 10.1109/tct.1963.1082116
^ Лоулер, Э. (1964), «Комментарий к минимальным наборам дуг обратной связи», IEEE Transactions on Circuit Theory , 11 (2): 296–297, doi : 10.1109/tct.1964.1082291
^ Перейти обратно: ^а ^б Бодлендер, Ханс Л .; Фомин Федор Владимирович; Костер, Арье MCA; Крач, Дитер; Тиликос, Димитриос М. (2012), «Заметка о точных алгоритмах для задач упорядочения вершин на графах», Theory of Computing Systems , 50 (3): 420–432, doi : 10.1007/s00224-011-9312-0 , hdl : 1956/4556 , МР 2885638 , S2CID 9967521
^ Чен, Цзянер; Лю, Ян; Лу, Сунцзянь; О'Салливан, Барри; Разгон, Игорь (2008), «Алгоритм с фиксированными параметрами для задачи множества вершин с направленной обратной связью», Журнал ACM , 55 (5): 1–19, doi : 10.1145/1411509.1411511 , S2CID 1547510
^ Бонами, Марта; Ковалик, Лукаш; Недерлоф, Йеспер; Пилипчук, Михал; Сокала, Аркадиуш; Врочна, Марцин (2018), «О множестве вершин с направленной обратной связью, параметризованном шириной дерева», в Брандштедте, Андреас; Кёлер, Эккехард; Меер, Клаус (ред.), Теоретико-графовые концепции в информатике - 44-й международный семинар, WG 2018, Котбус, Германия, 27–29 июня 2018 г., Труды , Конспекты лекций по информатике, том. 11159, Springer, стр. 65–78, arXiv : 1707.01470 , doi : 10.1007/978-3-030-00256-5_6 , S2CID 8008855
^ Лин, Лишин; Сахни, Сартадж (1989), «Проблемы справедливого удаления ребер», IEEE Transactions on Computers , 38 (5): 756–761, doi : 10.1109/12.24280 , MR 0994519
^ Швиковский, Бенно; Спекенмейер, Эвальд (2002), «О перечислении всех минимальных решений задач с обратной связью», Discrete Applied Mathematics , 117 (1–3): 253–265, doi : 10.1016/S0166-218X(00)00339-5 , MR 1881280
^ Перейти обратно: ^а ^б ^с Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Воегингер, Герхард (2000), «Набор дуг минимальной обратной связи» , сборник задач оптимизации NP , заархивировано из оригинала 29 июля 2021 г. , получено 29 июля 2021 г.
^ Идс, Питер ; Линь, Сюэмин; Смит, В.Ф. (1993), «Быстрая и эффективная эвристика для решения задачи множества дуг обратной связи» , Information Processing Letters , 47 (6): 319–323, doi : 10.1016/0020-0190(93)90079-O , MR 1256786 , заархивировано из оригинала 22 октября 2020 г. , получено 1 августа 2021 г.
^ Бергер, Бонни ; Шор, Питер В. (1997), «Точные границы для проблемы максимального ациклического подграфа», Журнал алгоритмов , 25 (1): 1–18, doi : 10.1006/jagm.1997.0864 , MR 1474592
^ Хассин, Рафаэль; Рубинштейн, Шломи (1994), «Приближения к проблеме максимального ациклического подграфа», Information Processing Letters , 51 (3): 133–140, doi : 10.1016/0020-0190(94)00086-7 , MR 1290207
^ Перейти обратно: ^а ^б Ньюман, Аланта (июнь 2000 г.), Аппроксимация максимального ациклического подграфа (магистерская диссертация), Массачусетский технологический институт, hdl : 1721.1/86548 , цитируется Гурусвами и др. (2011)
^ Перейти обратно: ^а ^б Габоу, Гарольд Н. (1995), «Центроиды, представления и субмодулярные потоки», Journal of Algorithms , 18 (3): 586–628, doi : 10.1006/jagm.1995.1022 , MR 1334365
^ Перейти обратно: ^а ^б Франк, Андраш (1981), «Как сделать орграф сильно связным», Combinatorica , 1 (2): 145–153, doi : 10.1007/BF02579270 , MR 0625547 , S2CID 27825518
^ Перейти обратно: ^а ^б Луккези, CL; Янгер, Д.Х. (1978), «Теорема о минимаксе для ориентированных графов», Журнал Лондонского математического общества , вторая серия, 17 (3): 369–374, doi : 10.1112/jlms/s2-17.3.369 , MR 0500618
^ Перейти обратно: ^а ^б Габоу, Гарольд Н. (1993), «Структура алгоритмов масштабирования стоимости для задач субмодульного потока», 34-й ежегодный симпозиум по основам информатики, Пало-Альто, Калифорния, США, 3-5 ноября 1993 г. , Компьютерное общество IEEE, стр. . 449–458, doi : 10.1109/SFCS.1993.366842 , MR 1328441 , S2CID 32162097.
^ Гретшель, Мартин ; Юнгер, Майкл; Рейнельт, Герхард (1985), «О многограннике ациклического подграфа», Mathematical Programming , 33 (1): 28–42, doi : 10.1007/BF01582009 , MR 0809747 , S2CID 206798683
^ Рамачандран, Виджая (1988), «Нахождение набора минимальной дуги обратной связи в приводимых потоковых графах», Journal of Algorithms , 9 (3): 299–313, doi : 10.1016/0196-6774(88)90022-3 , MR 0955140
^ Кеньон-Матье, Клэр ; Шуди, Уоррен (2007), «Как ранжировать с небольшим количеством ошибок: PTAS для дуги взвешенной обратной связи, установленной на турнирах», Джонсон, Дэвид С .; Файги, Уриэль (ред.), Труды 39-го ежегодного симпозиума ACM по теории вычислений, Сан-Диего, Калифорния, США, 11–13 июня 2007 г. , стр. 95–103, doi : 10.1145/1250790.1250806 , S2CID 9436948 , ECCC ТР06-144 ; см. также расширенную версию автора. Архивировано 15 января 2009 г. на Wayback Machine.
^ Арора, Санджив ; Фриз, Алан ; Каплан, Хаим (2002), «Новая процедура округления задачи назначения с применением к задачам плотного расположения графов» , Mathematical Programming , 92 (1): 1–36, doi : 10.1007/s101070100271 , MR 1892295 , S2CID 3207086 , в архиве из оригинала от 3 августа 2021 г. , получено 3 августа 2021 г.
^ Карп, Ричард М. (1972), «Сводимость комбинаторных задач», Сложность компьютерных вычислений , Proc. Симпозиумы. IBM Томас Дж. Уотсон Рез. Центр, Йорктаун-Хайтс, Нью-Йорк, Нью-Йорк: Пленум, стр. 85–103.
^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), «A1.1: GT8», Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, p. 192, ИСБН 0-7167-1045-5
^ Алон, Нога (2006), «Рейтинговые турниры», SIAM Journal on Discrete Mathematics , 20 (1): 137–142, doi : 10.1137/050623905 , MR 2257251
^ Шарби, Пьер; Томассе, Стефан; Йео, Андерс (2007), «Проблема с набором дуг минимальной обратной связи NP-сложна для турниров» (PDF) , Combinatorics, Probability and Computing , 16 (1): 1–4, doi : 10.1017/S0963548306007887 , MR 2282830 , S2CID 36539840
^ Озиелло, Г .; Д'Атри, А.; Протаси, М. (1980), «Сокращения, сохраняющие структуру среди задач выпуклой оптимизации», Журнал компьютерных и системных наук , 21 (1): 136–153, doi : 10.1016/0022-0000(80)90046-X , MR 0589808
^ Канн, Вигго (1992), Об аппроксимируемости задач NP-полной оптимизации (PDF) (докторская диссертация), Департамент численного анализа и вычислительной техники, Королевский технологический институт, Стокгольм, в архиве (PDF) с оригинала 29 декабря 2010 г. , получено 11 октября 2007 г.
^ Динур, Ирит ; Сафра, Сэмюэл (2005), «О сложности аппроксимации минимального вершинного покрытия» (PDF) , Annals of Mathematics , 162 (1): 439–485, doi : 10.4007/annals.2005.162.439 , заархивировано (PDF) из оригинал от 20 сентября 2009 г. , получено 29 июля 2021 г .; предварительная версия в Динур, Ирит ; Сафра, Сэмюэл (2002), «Важность предвзятости», в Рейфе, Джон Х. (ред.), Труды 34-го ежегодного симпозиума ACM по теории вычислений, 19–21 мая 2002 г., Монреаль, Квебек, Канада. , стр. 33–42, doi : 10.1145/509907.509915 , S2CID 1235048
^ Гурусвами, Венкатесан ; Хостад, Йохан ; Манокаран, Раджекар; Рагхавендра, Прасад; Чарикар, Моисей (2011), «Преодолеть случайный порядок сложно: каждый упорядочивающий CSP устойчив к аппроксимации» (PDF) , SIAM Journal on Computing , 40 (3): 878–914, doi : 10.1137/090756144 , MR 2823511 , в архиве (PDF) из оригинала 31 июля 2021 г. , получено 31 июля 2021 г.
^ Бонне, Эдуард; Пашос, Вангелис Т. (2018), «Разреженность и субэкспоненциальная аппроксимация», Acta Informatica , 55 (1): 1–15, arXiv : 1402.2843 , doi : 10.1007/s00236-016-0281-2 , MR 3757549 , S2CID 3136275
^ Ловас, Ласло (1976), «О двух минимаксных теоремах в графе», Журнал комбинаторной теории , серия B, 21 (2): 96–103, doi : 10.1016/0095-8956(76)90049-6 , MR 0427138
^ Бар-Ной, Амоц; Наор, Джозеф (1990), «Сортировка, наборы с минимальной обратной связью и пути Гамильтона в турнирах», SIAM Journal on Discrete Mathematics , 3 (1): 7–20, doi : 10.1137/0403002 , MR 1033709
^ Спенсер, Дж. (1980), «Оптимальное ранжирование турниров без рейтинга», Periodica Mathematica Hungarica , 11 (2): 131–144, doi : 10.1007/BF02017965 , MR 0573525 , S2CID 119894999
^ Фернандес де ла Вега, В. (1983), «О максимальной мощности согласованного набора дуг в случайном турнире», Журнал комбинаторной теории , серия B, 35 (3): 328–332, doi : 10.1016/0095 -8956(83)90060-6 , МР 0735201
^ Бартелеми, Жан-Пьер; Юдри, Оливье; Исаак, Гарт; Робертс, Фред С .; Тесман, Барри (1995), «Реверсивное число орграфа», Discrete Applied Mathematics , 60 (1–3): 39–76, doi : 10.1016/0166-218X(94)00042-C , MR 1339075
^ Исаак, Гарт; Нараян, Даррен А. (2004), «Классификация турниров, в которых ациклический турнир является минимальным набором дуг обратной связи» , Information Processing Letters , 92 (3): 107–111, doi : 10.1016/j.ipl.2004.07.001 , МР 2095357
^ Хуан, Хао; Ма, Цзе; Шапира, Асаф; Судаков, Бенни ; Юстер, Рафаэль (2013), «Большие множества дуг обратной связи, подграфы с высокой минимальной степенью и длинные циклы в эйлеровых орграфах», Combinatorics, Probability and Computing , 22 (6): 859–873, arXiv : 1202.2602 , doi : 10.1017/S0963548313000394 , hdl : 20.500.11850/73894 , MR 3111546 , S2CID 7967738
^ Ханауэр, Катрин; Бранденбург, Франц-Иосиф; Ауэр, Кристофер (2013), «Точные верхние границы для минимальных наборов дуг обратной связи регулярных графов», Брандштедт, Андреас; Янсен, Клаус; Райщук, Рюдигер (ред.), Теоретико-графовые концепции в информатике - 39-й международный семинар, WG 2013, Любек, Германия, 19–21 июня 2013 г., Пересмотренные статьи , Конспекты лекций по информатике, том. 8165, Springer, стр. 298–309, номер документа : 10.1007/978-3-642-45043-3_26 , MR 3139198.

[fivb-1] «Основная сетка – мужчины» , Рио, 2016 г. , Международная федерация волейбола , заархивировано из оригинала 23 декабря 2016 г. , получено 14 ноября 2021 г.

[hubert-2] Перейти обратно: ^а ^б ^с Хьюберт, Лоуренс (1976), «Сериация с использованием асимметричных мер близости», Британский журнал математической и статистической психологии , 29 (1): 32–52, doi : 10.1111/j.2044-8317.1976.tb00701.x , MR 0429180

[rt66-3] Перейти обратно: ^а ^б ^с Ремидж, Рассел-младший; Томпсон, Вашингтон-младший (1966), «Рейтинги парных сравнений максимального правдоподобия», Biometrika , 53 (1–2): 143–149, doi : 10.1093/biomet/53.1-2.143 , JSTOR 2334060 , MR 0196854 , PMID 5964054

[goddard-4] Годдард, Стивен Т. (1983), «Рейтинг в турнирах и групповом принятии решений», Management Science , 29 (12): 1384–1392, doi : 10.1287/mnsc.29.12.1384 , MR 0809110 ; обратите внимание, что алгоритм, предложенный Годдардом для определения рейтингов с минимальным нарушением, неверен.

[vdym-5] Вазири, Бабак; Дабадгао, Шонак; Да, Юверн; Морин, Томас Л. (январь 2018 г.), «Свойства методов спортивного ранжирования» (PDF) , Журнал Общества операционных исследований , 69 (5): 776–787, doi : 10.1057/s41274-017-0266-8 , S2CID 51887586

[cfr-6] Копперсмит, Дон ; Флейшер, Лиза К.; Рурда, Атри (2010), «Упорядочение по взвешенному количеству побед дает хороший рейтинг для взвешенных турниров», Транзакции ACM по алгоритмам , 6 (3): A55:1–A55:13, doi : 10.1145/1798596.1798608 , MR 2682624 , S2CID 18416

[seyfarth-7] Сейфарт, Роберт М. (ноябрь 1976 г.), «Социальные отношения среди взрослых самок павианов», Animal Behavior , 24 (4): 917–938, doi : 10.1016/s0003-3472(76)80022-x , S2CID 54284406

[drafthorse-8] Эстеп, DQ; Кроуэлл-Дэвис, СЛ; Эрл-Костелло, Южная Каролина; Бити, С.А. (январь 1993 г.), «Изменения в социальном поведении кобыл тяжеловозов (Equus caballus), совпадающие с вырождением жеребят», Applied Animal Behavior Science , 35 (3): 199–213, doi : 10.1016/0168-1591(93) 90137-э

[cockroach-9] Эйкворт, Джордж К. (апрель 2019 г.), «Доминирование таракана (науфоэта)», Поведение насекомых , CRC Press, стр. 120–126, doi : 10.1201/9780429049262-18 , S2CID 203898549

[slater-10] Слейтер, Патрик (1961), «Несоответствия в графике парных сравнений», Biometrika , 48 (3–4): 303–312, doi : 10.1093/biomet/48.3-4.303 , JSTOR 2332752

[brunk-11] Бранк, HD (1960), «Математические модели для ранжирования на основе парных сравнений», Журнал Американской статистической ассоциации , 55 (291): 503–520, doi : 10.2307/2281911 , JSTOR 2281911 , MR 0115242 ; опубликовано в предварительной форме как документ ASTIA № AD 206 573, ВВС США, Управление научных исследований, ноябрь 1958 г., hdl : 2027/mdp.39015095254010

[rt64-12] Томпсон, Вашингтон младший; Ремейдж, Рассел-младший (1964), «Рейтинги на основе парных сравнений», Annals of Mathematical Статистика , 35 (2): 739–747, doi : 10.1214/aoms/1177703572 , JSTOR 2238526 , MR 0161419

[kemeny-13] Кемени, Джон Г. (осень 1959 г.), «Математика без чисел», Дедал , 88 (4): 577–591, JSTOR 20026529

[KarpinskiSchudy-14] Перейти обратно: ^а ^б Карпински, Марек ; Шуди, Уоррен (2010), «Более быстрые алгоритмы для турнира по набору дуг обратной связи, агрегации рангов Кемени и турнира по промежуткам», в Чеонг, Отфрид ; Чва, Кён Ён; Пак, Кунсу (ред.), «Алгоритмы и вычисления – 21-й международный симпозиум», ISAAC 2010, остров Чеджу, Корея, 15–17 декабря 2010 г., Материалы, часть I , конспекты лекций по информатике, том. 6506, Springer, стр. 3–14, arXiv : 1006.4396 , doi : 10.1007/978-3-642-17517-6_3 , S2CID 16512997

[unger-15] Перейти обратно: ^а ^б Унгер, Стивен Х. (26 апреля 1957 г.), Исследование асинхронных сетей с логической обратной связью , Технические отчеты, том. 320, Массачусетский технологический институт, Исследовательская лаборатория электроники, hdl : 1721.1/4763

[clock-16] Ферер, Джон Р.; Джордан, Гарри Ф. (декабрь 1995 г.), «Размещение часовых вентилей во времяпролетных оптоэлектронных схемах», Applied Optics , 34 (35): 8125–8136, Bibcode : 1995ApOpt..34.8125F , doi : 10.1364/ao .34.008125 , PMID 21068927

[rh68-17] Розен, Эдвард М.; Хенли, Эрнест Дж. (лето 1968 г.), «Новая стехиометрия» , Chemical Engineering Education , 2 (3): 120–125, заархивировано из оригинала 02 августа 2021 г. , получено 2 августа 2021 г.

[dett98-18] Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), «Многослойные рисунки орграфов», Рисование графиков: алгоритмы визуализации графов , Прентис Холл , стр. 265–302, ISBN 978-0-13-301615-4

[bm01-19] Бастерт, Оливер; Матушевский, Кристиан (2001), «Многослойные рисунки орграфов», Кауфманн, Майкл; Вагнер, Доротея (ред.), Рисование графиков: методы и модели , Конспекты лекций по информатике, том. 2025, Springer-Verlag, стр. 87–120, номер документа : 10.1007/3-540-44969-8_5.

[df01-20] Деметреску, Камил; Финокки, Ирен (2001), «Разорвите «правильные» циклы и получите «лучший» рисунок», Журнал экспериментальной алгоритмики ACM , 6 : 171–182, MR 2027115.

[enss-21] Перейти обратно: ^а ^б ^с Эвен, Г.; Наор, Дж .; Шибер, Б .; Судан, М. (1998), «Аппроксимация наборов минимальной обратной связи и мультиразрезов в ориентированных графах», Algorithmica , 20 (2): 151–174, doi : 10.1007/PL00009191 , MR 1484534 , S2CID 2437790

[minoura-22] Перейти обратно: ^а ^б Минура, Тошими (1982), «Возвращение к предотвращению тупиков», Journal of the ACM , 29 (4): 1023–1048, doi : 10.1145/322344.322351 , MR 0674256 , S2CID 5284738

[missik-23] Мишра, Сунака; Сикдар, Крипасиндху (2004), «Об аппроксимируемости линейного порядка и связанных с ним задачах NP-оптимизации на графах», Discrete Applied Mathematics , 136 (2–3): 249–269, doi : 10.1016/S0166-218X(03)00444- Х , МР 2045215

[Hecht-24] Перейти обратно: ^а ^б Хехт, Майкл (2017), «Точные локализации наборов обратной связи», Теория вычислительных систем , 62 (5): 1048–1084, arXiv : 1702.07612 , doi : 10.1007/s00224-017-9777-6 , S2CID 18394348

[pa92-25] Парк, С.; Акерс, С.Б. (1992), «Эффективный метод поиска минимального набора дуг обратной связи в ориентированных графах», Труды Международного симпозиума IEEE по схемам и системам 1992 года (ISCAS '92) , том. 4, стр. 1863–1866, номер документа : 10.1109/iscas.1992.230449 , S2CID 122603659 .

[np00-26] Перейти обратно: ^а ^б Нутов, Зеев; Пенн, Михал (2000), «О целостности, устойчивости и составе упаковок и покрытий дициклов», Journal of Combinatorial Optimization , 4 (2): 235–251, doi : 10.1023/A:1009802905533 , MR 1772828 , S2CID 207632524

[younger-27] Янгер, Д. (1963), «Минимальные наборы дуг обратной связи для ориентированного графа», IEEE Transactions on Circuit Theory , 10 (2): 238–245, doi : 10.1109/tct.1963.1082116

[lawler-28] Лоулер, Э. (1964), «Комментарий к минимальным наборам дуг обратной связи», IEEE Transactions on Circuit Theory , 11 (2): 296–297, doi : 10.1109/tct.1964.1082291

[bfkkt-29] Перейти обратно: ^а ^б Бодлендер, Ханс Л .; Фомин Федор Владимирович; Костер, Арье MCA; Крач, Дитер; Тиликос, Димитриос М. (2012), «Заметка о точных алгоритмах для задач упорядочения вершин на графах», Theory of Computing Systems , 50 (3): 420–432, doi : 10.1007/s00224-011-9312-0 , hdl : 1956/4556 , МР 2885638 , S2CID 9967521

[cllor-30] Чен, Цзянер; Лю, Ян; Лу, Сунцзянь; О'Салливан, Барри; Разгон, Игорь (2008), «Алгоритм с фиксированными параметрами для задачи множества вершин с направленной обратной связью», Журнал ACM , 55 (5): 1–19, doi : 10.1145/1411509.1411511 , S2CID 1547510

[bknpsw-31] Бонами, Марта; Ковалик, Лукаш; Недерлоф, Йеспер; Пилипчук, Михал; Сокала, Аркадиуш; Врочна, Марцин (2018), «О множестве вершин с направленной обратной связью, параметризованном шириной дерева», в Брандштедте, Андреас; Кёлер, Эккехард; Меер, Клаус (ред.), Теоретико-графовые концепции в информатике - 44-й международный семинар, WG 2018, Котбус, Германия, 27–29 июня 2018 г., Труды , Конспекты лекций по информатике, том. 11159, Springer, стр. 65–78, arXiv : 1707.01470 , doi : 10.1007/978-3-030-00256-5_6 , S2CID 8008855

[ls89-32] Лин, Лишин; Сахни, Сартадж (1989), «Проблемы справедливого удаления ребер», IEEE Transactions on Computers , 38 (5): 756–761, doi : 10.1109/12.24280 , MR 0994519

[ss02-33] Швиковский, Бенно; Спекенмейер, Эвальд (2002), «О перечислении всех минимальных решений задач с обратной связью», Discrete Applied Mathematics , 117 (1–3): 253–265, doi : 10.1016/S0166-218X(00)00339-5 , MR 1881280

[compendium-34] Перейти обратно: ^а ^б ^с Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Воегингер, Герхард (2000), «Набор дуг минимальной обратной связи» , сборник задач оптимизации NP , заархивировано из оригинала 29 июля 2021 г. , получено 29 июля 2021 г.

[els-35] Идс, Питер ; Линь, Сюэмин; Смит, В.Ф. (1993), «Быстрая и эффективная эвристика для решения задачи множества дуг обратной связи» , Information Processing Letters , 47 (6): 319–323, doi : 10.1016/0020-0190(93)90079-O , MR 1256786 , заархивировано из оригинала 22 октября 2020 г. , получено 1 августа 2021 г.

[bs97-36] Бергер, Бонни ; Шор, Питер В. (1997), «Точные границы для проблемы максимального ациклического подграфа», Журнал алгоритмов , 25 (1): 1–18, doi : 10.1006/jagm.1997.0864 , MR 1474592

[hr94-37] Хассин, Рафаэль; Рубинштейн, Шломи (1994), «Приближения к проблеме максимального ациклического подграфа», Information Processing Letters , 51 (3): 133–140, doi : 10.1016/0020-0190(94)00086-7 , MR 1290207

[newman-38] Перейти обратно: ^а ^б Ньюман, Аланта (июнь 2000 г.), Аппроксимация максимального ациклического подграфа (магистерская диссертация), Массачусетский технологический институт, hdl : 1721.1/86548 , цитируется Гурусвами и др. (2011)

[gab95-39] Перейти обратно: ^а ^б Габоу, Гарольд Н. (1995), «Центроиды, представления и субмодулярные потоки», Journal of Algorithms , 18 (3): 586–628, doi : 10.1006/jagm.1995.1022 , MR 1334365

[frank-40] Перейти обратно: ^а ^б Франк, Андраш (1981), «Как сделать орграф сильно связным», Combinatorica , 1 (2): 145–153, doi : 10.1007/BF02579270 , MR 0625547 , S2CID 27825518

[ly78-41] Перейти обратно: ^а ^б Луккези, CL; Янгер, Д.Х. (1978), «Теорема о минимаксе для ориентированных графов», Журнал Лондонского математического общества , вторая серия, 17 (3): 369–374, doi : 10.1112/jlms/s2-17.3.369 , MR 0500618

[gab93-42] Перейти обратно: ^а ^б Габоу, Гарольд Н. (1993), «Структура алгоритмов масштабирования стоимости для задач субмодульного потока», 34-й ежегодный симпозиум по основам информатики, Пало-Альто, Калифорния, США, 3-5 ноября 1993 г. , Компьютерное общество IEEE, стр. . 449–458, doi : 10.1109/SFCS.1993.366842 , MR 1328441 , S2CID 32162097.

[gjr85-43] Гретшель, Мартин ; Юнгер, Майкл; Рейнельт, Герхард (1985), «О многограннике ациклического подграфа», Mathematical Programming , 33 (1): 28–42, doi : 10.1007/BF01582009 , MR 0809747 , S2CID 206798683

[ramachandran-44] Рамачандран, Виджая (1988), «Нахождение набора минимальной дуги обратной связи в приводимых потоковых графах», Journal of Algorithms , 9 (3): 299–313, doi : 10.1016/0196-6774(88)90022-3 , MR 0955140

[MathieuSchudy-45] Кеньон-Матье, Клэр ; Шуди, Уоррен (2007), «Как ранжировать с небольшим количеством ошибок: PTAS для дуги взвешенной обратной связи, установленной на турнирах», Джонсон, Дэвид С .; Файги, Уриэль (ред.), Труды 39-го ежегодного симпозиума ACM по теории вычислений, Сан-Диего, Калифорния, США, 11–13 июня 2007 г. , стр. 95–103, doi : 10.1145/1250790.1250806 , S2CID 9436948 , ECCC ТР06-144 ; см. также расширенную версию автора. Архивировано 15 января 2009 г. на Wayback Machine.

[afk02-46] Арора, Санджив ; Фриз, Алан ; Каплан, Хаим (2002), «Новая процедура округления задачи назначения с применением к задачам плотного расположения графов» , Mathematical Programming , 92 (1): 1–36, doi : 10.1007/s101070100271 , MR 1892295 , S2CID 3207086 , в архиве из оригинала от 3 августа 2021 г. , получено 3 августа 2021 г.

[karp-47] Карп, Ричард М. (1972), «Сводимость комбинаторных задач», Сложность компьютерных вычислений , Proc. Симпозиумы. IBM Томас Дж. Уотсон Рез. Центр, Йорктаун-Хайтс, Нью-Йорк, Нью-Йорк: Пленум, стр. 85–103.

[gj79-48] Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), «A1.1: GT8», Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, p. 192, ИСБН 0-7167-1045-5

[alon-49] Алон, Нога (2006), «Рейтинговые турниры», SIAM Journal on Discrete Mathematics , 20 (1): 137–142, doi : 10.1137/050623905 , MR 2257251

[cty-50] Шарби, Пьер; Томассе, Стефан; Йео, Андерс (2007), «Проблема с набором дуг минимальной обратной связи NP-сложна для турниров» (PDF) , Combinatorics, Probability and Computing , 16 (1): 1–4, doi : 10.1017/S0963548306007887 , MR 2282830 , S2CID 36539840

[adp80-51] Озиелло, Г .; Д'Атри, А.; Протаси, М. (1980), «Сокращения, сохраняющие структуру среди задач выпуклой оптимизации», Журнал компьютерных и системных наук , 21 (1): 136–153, doi : 10.1016/0022-0000(80)90046-X , MR 0589808

[kann-52] Канн, Вигго (1992), Об аппроксимируемости задач NP-полной оптимизации (PDF) (докторская диссертация), Департамент численного анализа и вычислительной техники, Королевский технологический институт, Стокгольм, в архиве (PDF) с оригинала 29 декабря 2010 г. , получено 11 октября 2007 г.

[ds05-53] Динур, Ирит ; Сафра, Сэмюэл (2005), «О сложности аппроксимации минимального вершинного покрытия» (PDF) , Annals of Mathematics , 162 (1): 439–485, doi : 10.4007/annals.2005.162.439 , заархивировано (PDF) из оригинал от 20 сентября 2009 г. , получено 29 июля 2021 г .; предварительная версия в Динур, Ирит ; Сафра, Сэмюэл (2002), «Важность предвзятости», в Рейфе, Джон Х. (ред.), Труды 34-го ежегодного симпозиума ACM по теории вычислений, 19–21 мая 2002 г., Монреаль, Квебек, Канада. , стр. 33–42, doi : 10.1145/509907.509915 , S2CID 1235048

[ghmrc-54] Гурусвами, Венкатесан ; Хостад, Йохан ; Манокаран, Раджекар; Рагхавендра, Прасад; Чарикар, Моисей (2011), «Преодолеть случайный порядок сложно: каждый упорядочивающий CSP устойчив к аппроксимации» (PDF) , SIAM Journal on Computing , 40 (3): 878–914, doi : 10.1137/090756144 , MR 2823511 , в архиве (PDF) из оригинала 31 июля 2021 г. , получено 31 июля 2021 г.

[bp18-55] Бонне, Эдуард; Пашос, Вангелис Т. (2018), «Разреженность и субэкспоненциальная аппроксимация», Acta Informatica , 55 (1): 1–15, arXiv : 1402.2843 , doi : 10.1007/s00236-016-0281-2 , MR 3757549 , S2CID 3136275

[lovasz-56] Ловас, Ласло (1976), «О двух минимаксных теоремах в графе», Журнал комбинаторной теории , серия B, 21 (2): 96–103, doi : 10.1016/0095-8956(76)90049-6 , MR 0427138

[bn90-57] Бар-Ной, Амоц; Наор, Джозеф (1990), «Сортировка, наборы с минимальной обратной связью и пути Гамильтона в турнирах», SIAM Journal on Discrete Mathematics , 3 (1): 7–20, doi : 10.1137/0403002 , MR 1033709

[spencer-58] Спенсер, Дж. (1980), «Оптимальное ранжирование турниров без рейтинга», Periodica Mathematica Hungarica , 11 (2): 131–144, doi : 10.1007/BF02017965 , MR 0573525 , S2CID 119894999

[fdlv-59] Фернандес де ла Вега, В. (1983), «О максимальной мощности согласованного набора дуг в случайном турнире», Журнал комбинаторной теории , серия B, 35 (3): 328–332, doi : 10.1016/0095 -8956(83)90060-6 , МР 0735201

[bhirt-60] Бартелеми, Жан-Пьер; Юдри, Оливье; Исаак, Гарт; Робертс, Фред С .; Тесман, Барри (1995), «Реверсивное число орграфа», Discrete Applied Mathematics , 60 (1–3): 39–76, doi : 10.1016/0166-218X(94)00042-C , MR 1339075

[in04-61] Исаак, Гарт; Нараян, Даррен А. (2004), «Классификация турниров, в которых ациклический турнир является минимальным набором дуг обратной связи» , Information Processing Letters , 92 (3): 107–111, doi : 10.1016/j.ipl.2004.07.001 , МР 2095357

[hmssy-62] Хуан, Хао; Ма, Цзе; Шапира, Асаф; Судаков, Бенни ; Юстер, Рафаэль (2013), «Большие множества дуг обратной связи, подграфы с высокой минимальной степенью и длинные циклы в эйлеровых орграфах», Combinatorics, Probability and Computing , 22 (6): 859–873, arXiv : 1202.2602 , doi : 10.1017/S0963548313000394 , hdl : 20.500.11850/73894 , MR 3111546 , S2CID 7967738

[hba-63] Ханауэр, Катрин; Бранденбург, Франц-Иосиф; Ауэр, Кристофер (2013), «Точные верхние границы для минимальных наборов дуг обратной связи регулярных графов», Брандштедт, Андреас; Янсен, Клаус; Райщук, Рюдигер (ред.), Теоретико-графовые концепции в информатике - 39-й международный семинар, WG 2013, Любек, Германия, 19–21 июня 2013 г., Пересмотренные статьи , Конспекты лекций по информатике, том. 8165, Springer, стр. 298–309, номер документа : 10.1007/978-3-642-45043-3_26 , MR 3139198.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]

[61]

[62]

[63]