Вырождение (теория графов) - Degeneracy (graph theory)

«K-core» перенаправляется сюда. В основной графа - это другое понятие.

2-вырожденный граф: каждая вершина имеет не более двух соседей слева, поэтому самая правая вершина любого подграфа имеет степень не более двух. Его 2-ядерный подграф, оставшийся после многократного удаления вершин степени меньше двух, закрашен.

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

Вырождение также известно как kномер ядра,^[1] ширина,^[2] и связь,^[3] и по сути такой же, как цветное число^[4] или же Число Секереса-Вильфа (названный в честь Секереш и Уилф  (1968 )). k-вырожденные графы также назывались k-индуктивные графики.^[5] Вырождение графа можно вычислить в линейное время алгоритмом, многократно удаляющим вершины минимальной степени.^[6] В связанные компоненты которые остаются после всех вершин степени меньше k были удалены, называются k-очки графа и вырожденность графа - наибольшее значение k такой, что у него есть k-основной.

Примеры

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

Каждый конечный планарный граф имеет вершину пятой степени или меньше; следовательно, каждый плоский граф является 5-вырожденным, а вырожденность любого плоского графа не превосходит пяти. Точно так же каждый внешнепланарный граф имеет вырождение не более двух,^[7] и Аполлонические сети есть вырождение три.

В Модель Барабаши – Альберта для создания случайный безмасштабные сети^[8] параметризуется числом м такая, что каждая добавляемая к графу вершина имеет м ранее добавленные вершины. Отсюда следует, что любой подграф образованной таким образом сети имеет вершину степени не выше м (последняя вершина в подграфе, которая была добавлена ​​к графу) и сети Барабаши – Альберта автоматически м-вырожденный.

Каждый k-регулярный граф имеет вырождение ровноk. Более того, вырожденность графа равна его максимальной степени вершины тогда и только тогда, когда хотя бы одна из связанные компоненты графа регулярна максимальной степени. Для всех остальных графов вырождение строго меньше максимальной степени.^[9]

Определения и эквиваленты

Число раскраски графа грамм был определен Эрдеш и Хайнал (1966) быть наименьшим κ, для которого существует упорядочение вершин грамм в котором каждая вершина имеет меньше, чем κ соседей, находящихся в более раннем порядке. Его следует отличать от хроматическое число из грамм, минимальное количество цветов, необходимое для раскраски вершин, чтобы никакие две соседние вершины не имели одинаковый цвет; порядок, определяющий номер окраски, обеспечивает порядок окраски вершин G в номер окраски, но в целом хроматическое число может быть меньше.

Вырождение графа грамм был определен Лизать и белый (1970) как минимум k так что каждый индуцированный подграф из грамм содержит вершину с k или меньше соседей. Определение будет таким же, если произвольные подграфы разрешены вместо индуцированных подграфов, поскольку неиндуцированный подграф может иметь только степени вершин, которые меньше или равны степеням вершин в подграфе, индуцированном тем же множеством вершин.

Два понятия числа раскраски и вырождения эквивалентны: в любом конечном графе вырождение всего на единицу меньше числа раскраски.^[10] В самом деле, если граф имеет порядок с числом раскраски κ, то в каждом подграфе ЧАС вершина, принадлежащая ЧАС и последний в порядке имеет не более κ - 1 соседей в ЧАС. В обратном направлении, если грамм является k-вырожденный, то упорядочивание с раскраской номера k +1 можно получить, многократно находя вершину v максимум с k соседи, убирая v из графа, упорядочивая оставшиеся вершины и добавляя v до конца заказа.

Третья, эквивалентная формулировка: грамм является k-вырожденный (или имеет цветное число не более k + 1) тогда и только тогда, когда ребра грамм могут быть ориентированы на формирование ориентированный ациклический граф с превосходить в большинстве k.^[11] Такая ориентация может быть сформирована путем ориентации каждого края по направлению к более ранней из двух его конечных точек в порядке цветного номера. В обратном направлении, если ориентация с исходящей степенью k дан заказ с раскраской номера k +1 можно получить как топологический порядок полученного ориентированного ациклического графа.

k-Ядра

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

Вершина ${\displaystyle u}$ имеет сердцевина ${\displaystyle c}$ если он принадлежит${\displaystyle c}$-кор, но не ни к какому ${\displaystyle (c+1)}$-основной.

Концепция k-core был введен для изучения кластерной структуры социальные сети^[12] и описать эволюцию случайные графы.^[13] Он также применялся в биоинформатика,^[14] визуализация сети,^[15] Интернет-структура,^[16] распространение экономических кризисов,^[17] выявление влиятельных распространителей,^[18] структура коры головного мозга^[19] или устойчивость сетей в экология.^[20] Расширения k-основные структуры в взвешенных сетях также были разработаны.^[21] Обзор темы, охватывающий основные концепции, важные алгоритмические методы, а также некоторые области применения, можно найти в Malliaros et al. (2019).

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

Алгоритмы

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

Более подробно алгоритм работает следующим образом:

• Инициализировать выходной список L.
• Вычислить число d_v для каждой вершины v в грамм, количество соседей v которые еще не в L. Изначально эти числа - это просто степени вершин.
• Инициализировать массив D такой, что D[я] содержит список вершин v которые еще не в L для которого d_v = я.
• Инициализировать k до 0.
• Повторение п раз:
  • Сканировать ячейки массива D[0], D[1], ... пока не найдете я для которого D[я] непусто.
  • Набор k до макс (k,я)
  • Выберите вершину v из D[я]. Добавлять v к началу L и удалите его из D[я].
  • Для каждого соседа ш из v еще не в L, вычтите один из d_ш и двигаться ш в ячейку D, соответствующую новому значению d_ш.

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

Инициализация переменных L, d_v, D, и k можно легко сделать за линейное время. Поиск каждой последовательно удаляемой вершины v и корректировка ячеек D содержащий соседей v занять время, пропорциональное стоимости d_v на этом этапе; но сумма этих значений - это количество ребер графа (каждое ребро вносит вклад в член суммы для более поздней из двух его конечных точек), поэтому общее время является линейным.

Связь с другими параметрами графика

Если график грамм ориентирован ациклически с исходящей степенью k, то его ребра можно разбить на k леса путем выбора одного леса для каждого исходящего края каждого узла. Таким образом родословие из грамм не больше, чем его вырождение. В другом направлении п-вершинный граф, который можно разбить на k леса не более k(п - 1) ребра и, следовательно, имеет вершину степени не выше 2k- 1 - таким образом, вырожденность меньше двукратной древовидности. Можно также вычислить за полиномиальное время ориентацию графа, которая минимизирует исходящую степень, но не обязательно должна быть ациклической. Ребра графа с такой ориентацией можно таким же образом разбить на k псевдолеса, и, наоборот, любое разбиение ребер графа на k псевдолеса приводит к удалениюk ориентации (выбирая ориентацию исходящей степени-1 для каждого псевдолеса), поэтому минимальная степень исходящей такой ориентации равна псевдоарборичность, что опять же не более чем равно вырождению.^[26] В толщина также находится в пределах постоянного множителя древовидности и, следовательно, вырождения.^[27]

А k-вырожденный граф имеет хроматическое число не более k + 1; это доказывается простой индукцией по количеству вершин, что в точности похоже на доказательство теоремы о шести цветах для плоских графов. Поскольку хроматическое число является верхней границей порядка максимальная клика, последний инвариант также не выше вырождения плюс один. Используя жадная окраска алгоритма упорядочивания с оптимальным номером раскраски, можно цвет графика а k-вырожденный граф, используя не более k + 1 цвет.^[28]

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

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

В Гипотеза Берра – Эрдеша связывает вырождение графа грамм к Число Рамсея из грамм, в мере п такая, что любая двухреберная раскраска п-вертекс полный график должен содержать монохромную копию грамм. В частности, гипотеза состоит в том, что для любого фиксированного значения k, число Рамсея k-вырожденных графов линейно растет по количеству вершин графов.^[31] Гипотеза была доказана Ли (2017).

Бесконечные графы

Хотя понятия вырожденности и числа раскраски часто рассматриваются в контексте конечных графов, исходная мотивация для Эрдеш и Хайнал (1966) была теория бесконечных графов. Для бесконечного графа грамм, можно определить число раскраски аналогично определению для конечных графов, как наименьшее количественное числительное α такой, что существует хороший порядок вершин грамм в котором каждая вершина имеет меньше, чем α соседей, находящихся в более раннем порядке. Неравенство между раскраской и хроматическими числами сохраняется и в этой бесконечной установке; Эрдеш и Хайнал (1966) заявляют, что на момент публикации их статьи об этом уже было хорошо известно.

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

Смотрите также

• Теория графов
• Сетевая наука
• Теория перколяции
• Структура ядро ​​– периферия
• Гипотеза Сереседы

Примечания

1. Бадер и Хог (2003).
2. Фрейдер (1982).
3. Кирусис и Тиликос (1996).
4. Эрдеш и Хайнал (1966).
5. Иранский (1994).
6. Матула и Бек (1983).
7. Лизать и белый (1970).
8. Барабаши и Альберт (1999).
9. Дженсен и Тофт (2011), п. 78: "Легко увидеть, что col (грамм) = Δ (грамм) + 1 тогда и только тогда, когда грамм имеет Δ (грамм) -регулярный компонент. "В обозначениях, используемых Дженсеном и Тофтом, col (грамм) - вырождение плюс один, а Δ (грамм) - максимальная степень вершины.
10. Матула (1968); Лизать и белый (1970), Предложение 1, стр. 1084.
11. Хробак и Эппштейн (1991).
12. Зайдман (1983).
13. Боллобаш (1984); Лучак (1991);Дороговцев, Гольцев и Мендес (2006).
14. Бадер и Хог (2003); Алтаф-Уль-Амин и др. (2003); Wuchty & Almaas (2005).
15. Гертлер и Патриньяни (2004); Альварес-Хамелин и др. (2006).
16. Carmi et al. (2007).
17. Garas et al. (2010).
18. Kitsak et al. (2010).
19. Lahav et al. (2016).
20. Гарсия-Альгарра и др. (2017).
21. Гарас, Швейцер и Хэвлин (2012).
22. Balogh et al. (2012).
23. Киркпатрик и др. (2002).
24. Адлер (1991).
25. Брутто, B; Санхедрай, H; Шехтман, Л; Хэвлин, S (2020). «Взаимосвязи между сетями действуют как внешнее поле при перколяционных переходах первого порядка». Физический обзор E. 101 (2). arXiv:1905.07009. Дои:10.1103 / PhysRevE.101.022316.
26. Хробак и Эппштейн (1991); Габоу и Вестерманн (1992); Венкатесваран (2004); Асахиро и др. (2006); Ковалик (2006).
27. Дин, Хатчинсон и Шайнерман (1991).
28. Эрдеш и Хайнал (1966); Секерес и Вильф (1968).
29. Moody & White (2003).
30. Робертсон и Сеймур (1984).
31. Бёрр и Эрдеш (1975).

Рекомендации

• Адлер, Жанна (1991), "Перколяция бутстрапа", Physica A: Статистическая механика и ее приложения, 171 (3): 453–470, Bibcode:1991PhyA..171..453A, Дои:10.1016 / 0378-4371 (91) 90295-н
• Алтаф-Уль-Амин, М .; Нишиката, К .; Кома, Т .; Miyasato, T .; Shinbo, Y .; Arifuzzaman, M .; Wada, C .; Maeda, M .; Осима, Т. (2003), "Прогнозирование функций белков на основе k-системы белок-белковых взаимодействий и аминокислотные последовательности » (PDF), Геномная информатика, 14: 498–499, архивировано с оригинал (PDF) на 2007-09-27
• Альварес-Хамелин, Хосе Игнасио; Далл'Аста, Лука; Баррат, Ален; Веспиньяни, Алессандро (2006), "kразложение ядра: инструмент для визуализации крупномасштабных сетей », Вайс, Яир; Шёлкопф, Бернхард; Платт, Джон (ред.), Достижения в системах обработки нейронной информации 18: Материалы конференции 2005 г., 18, MIT Press, стр. 41, arXiv:cs / 0504107, Bibcode:2005cs ........ 4107A, ISBN  0262232537
• Асахиро, Юичи; Мияно, Эйдзи; Оно, Хиротака; Zenmyo, Kouhei (2006), "Алгоритмы ориентации графа для минимизации максимальной исходящей степени", CATS '06: Материалы 12-го вычислительного симпозиума: Австралазийский симпозиум по теории, Дарлингхерст, Австралия, Австралия: Австралийское компьютерное общество, Inc., стр. 11–20, ISBN  1-920682-33-3
• Бадер, Гэри Д.; Хог, Кристофер В. В. (2003), «Автоматический метод поиска молекулярных комплексов в больших сетях взаимодействия белков», BMC Bioinformatics, 4 (1): 2, Дои:10.1186/1471-2105-4-2, ЧВК  149346, PMID  12525261
• Балог, Йожеф; Боллобаш, Бела; Думинил-Копен, Гюго; Моррис, Роберт (2012), «Острый порог бутстраповской перколяции во всех измерениях», Труды Американского математического общества, 364 (5): 2667–2701, arXiv:1010.3326, Дои:10.1090 / S0002-9947-2011-05552-2, МИСТЕР  2888224
• Барабаши, Альберт-Ласло; Альберт, Река (1999), «Появление масштабирования в случайных сетях» (PDF), Наука, 286 (5439): 509–512, arXiv:cond-mat / 9910332, Bibcode:1999Научный ... 286..509Б, Дои:10.1126 / science.286.5439.509, PMID  10521342, заархивировано из оригинал (PDF) на 2006-11-11
• Боллобаш, Бела (1984), «Эволюция разреженных графов», Теория графов и комбинаторика, Proc. Кембриджская комбинаторная конференция. в честь Пола Эрдёша, Academic Press, стр. 35–57.
• Берр, Стефан А.; Эрдеш, Пол (1975), "О величине обобщенных чисел Рамсея для графиков", Бесконечные и конечные множества (Colloq., Keszthely, 1973; посвящается П. Эрдёшу в день его 60-летия), Vol. 1 (PDF), Коллок. Математика. Soc. Янош Бойяи, 10, Амстердам: Северная Голландия, стр. 214–240, МИСТЕР  0371701
• Carmi, S .; Havlin, S .; Киркпатрик, S .; Shavitt, Y .; Шир, Э. (2007), "Модель топологии Интернета с использованием декомпозиции k-оболочки", Труды Национальной академии наук, 104 (27): 11150–11154, arXiv:cs / 0607080, Bibcode:2007PNAS..10411150C, Дои:10.1073 / pnas.0701175104, ЧВК  1896135, PMID  17586683
• Хробак, Марек; Эппштейн, Дэвид (1991), «Планарные ориентации с низкой степенью выхода и уплотнением матриц смежности» (PDF), Теоретическая информатика, 86 (2): 243–266, Дои:10.1016/0304-3975(91)90020-3
• Дин, Алиса М .; Хатчинсон, Джоан П.; Шайнерман, Эдвард Р. (1991), «О толщине и древовидности графика», Журнал комбинаторной теории, Серия B, 52 (1): 147–151, Дои:10.1016 / 0095-8956 (91) 90100-Х, МИСТЕР  1109429
• Дороговцев, С. Н .; Гольцев, А. В .; Мендес, Дж. Ф. Ф. (2006) "k-корпоративная организация сложных сетей », Письма с физическими проверками, 96 (4): 040601, arXiv:cond-mat / 0509102, Bibcode:2006PhRvL..96d0601D, Дои:10.1103 / PhysRevLett.96.040601, PMID  16486798
• Эрдеш, Пол; Хайнал, Андраш (1966), «О хроматическом числе графов и систем множеств» (PDF), Acta Mathematica Hungarica, 17 (1–2): 61–99, Дои:10.1007 / BF02020444, МИСТЕР  0193025
• Фрейдер, Юджин К. (1982), "Достаточное условие для поиска без возврата", Журнал ACM, 29 (1): 24–32, Дои:10.1145/322290.322292
• Gabow, H.N .; Вестерманн, Х. Х. (1992), "Леса, фреймы и игры: алгоритмы для матроидных сумм и приложений", Алгоритмика, 7 (1): 465–497, Дои:10.1007 / BF01758774
• Гертлер, Марко; Патриньяни, Маурицио (2004), "Динамический анализ графа автономной системы", Proc. 2-й международный семинар по междоменной производительности и моделированию (IPS 2004), стр. 13–24, CiteSeerX  10.1.1.81.6841
• Гарас, Антониос; Аргиракис, Панос; Розенблат, Селин; Томассини, Марко; Хавлин, Шломо (2010), «Мировое распространение экономического кризиса», Новый журнал физики, 12 (11): 113043, arXiv:1008.3893, Bibcode:2010NJPh ... 12k3043G, Дои:10.1088/1367-2630/12/11/113043
• Гарас, Антониос; Швейцер, Франк; Хавлин, Шломо (2012), "Метод декомпозиции Ak-оболочки для взвешенных сетей", Новый журнал физики, 14 (8): 083030, arXiv:1205.3720, Bibcode:2012НДЖФ ... 14х3030Г, Дои:10.1088/1367-2630/14/8/083030
• Гарсия-Альгарра, Хавьер; Пастор Хуан Мануэль; Ириондо, Хосе Мария; Галеано, Хавьер (2017), «Ранжирование критических видов для сохранения функциональности мутуалистических сетей с использованием k-корпоральное разложение », PeerJ, 5: e3321, Дои:10.7717 / peerj.3321, ЧВК  5438587, PMID  28533969
• Ирани, Сэнди (1994), "Раскраска индуктивных графиков в режиме онлайн", Алгоритмика, 11 (1): 53–72, Дои:10.1007 / BF01294263
• Дженсен, Томми Р .; Тофт, Бьярн (2011), Проблемы с раскраской графиков, Ряд Уайли по дискретной математике и оптимизации, 39, Джон Уайли и сыновья, ISBN  9781118030745
• Киркпатрик, Скотт; Wilcke, Winfried W .; Гарнер, Роберт Б .; Хуэлс, Харальд (2002), "Перколяция в плотных массивах хранения", Physica A: Статистическая механика и ее приложения, 314 (1–4): 220–229, Bibcode:2002PhyA..314..220K, Дои:10.1016 / S0378-4371 (02) 01153-6, МИСТЕР  1961703
• Kirousis, L.M .; Тиликос, Д. М. (1996), «Связь графа» (PDF), SIAM Журнал по вычислениям, 25 (3): 626–647, Дои:10.1137 / S0097539793255709, заархивировано из оригинал (PDF) на 2011-07-21
• Кицак, Максим; Gallos, Lazaros K .; Хавлин, Шломо; Лильерос, Фредрик; Мучник, Лев; Стэнли, Х. Юджин; Максе, Эрнан А. (29 августа 2010 г.), «Выявление влиятельных распространителей в сложных сетях», Природа Физика, 6 (11): 888–893, arXiv:1001.5285, Bibcode:2010НатФ ... 6..888K, Дои:10.1038 / nphys1746
• Ковалик, Лукаш (2006), "Схема аппроксимации для определения наименьшей исходящей степени ориентации и мер плотности графа", Труды 17-го Международного симпозиума по алгоритмам и вычислениям (ISAAC 2006), Конспект лекций по информатике, Springer-Verlag, 4288: 557–566, Дои:10.1007/11940128_56, ISBN  978-3-540-49694-6
• Лахав, Нир; Кшерим, Варух; Бен-Саймон, Эти; Марон-Кац, Ади; Коэн, Реувен; Хавлин, Шломо (2016), "K-разложение оболочки раскрывает иерархическую корковую организацию человеческого мозга », Новый журнал физики, 18 (8): 083013, arXiv:1803.03742, Bibcode:2016NJPh ... 18h3013L, Дои:10.1088/1367-2630/18/8/083013
• Ли, Чунгбум (2017), «Числа Рамсея вырожденных графов», Анналы математики, 185 (3): 791–829, arXiv:1505.04773, Дои:10.4007 / анналы.2017.185.3.2
• Лик, Дон Р .; Уайт, Артур Т. (1970) "k-вырожденные графы », Канадский математический журнал, 22: 1082–1096, Дои:10.4153 / CJM-1970-125-1
• Лучак, Томаш (1991), "Размер и возможности подключения k-ядро случайного графа », Дискретная математика, 91 (1): 61–68, Дои:10.1016 / 0012-365Х (91) 90162-У
• Malliaros, Fragkiskos D .; Гиацидис, Христос; Пападопулос, Апостолос Н .; Вазирджаннис, Михалис (2019), «Базовая декомпозиция сетей: теория, алгоритмы и приложения» (PDF), Журнал VLDB, Дои:10.1007 / s00778-019-00587-4
• Матула, Дэвид В. (1968), «Теорема о минимуме и максимуме для графов с применением к раскраске графов», Национальное собрание SIAM 1968, SIAM Обзор, 10 (4): 481–482, Дои:10.1137/1010115
• Матула, Дэвид В .; Бек, Л. Л. (1983), "Алгоритмы наименьшего последнего упорядочения, кластеризации и раскраски графов", Журнал ACM, 30 (3): 417–427, Дои:10.1145/2402.322385, МИСТЕР  0709826
• Муди, Джеймс; Уайт, Дуглас Р. (2003), «Структурная сплоченность и встроенность: иерархическая концепция социальных групп», Американский социологический обзор, 68 (1): 1–25, Дои:10.2307/3088904, JSTOR  3088904
• Робертсон, Нил; Сеймур, Пол (1984), "Миноры графа. III. Плоская ширина дерева", Журнал комбинаторной теории, Серия B, 36 (1): 49–64, Дои:10.1016/0095-8956(84)90013-3
• Сейдман, Стивен Б. (1983), "Сетевая структура и минимальная степень", Социальные сети, 5 (3): 269–287, Дои:10.1016 / 0378-8733 (83) 90028-Х
• Секерес, Джордж; Уилф, Герберт С. (1968), «Неравенство для хроматического числа графа», Журнал комбинаторной теории, 4: 1–3, Дои:10.1016 / S0021-9800 (68) 80081-X
• Венкатесваран, В. (2004), «Минимизация максимальной степени», Дискретная прикладная математика, 143 (1–3): 374–378, Дои:10.1016 / j.dam.2003.07.007
• Wuchty, S .; Алмаас, Э. (2005), «Очистка дрожжевой белковой сети», Протеомика, 5 (2): 444–449, Дои:10.1002 / pmic.200400962, PMID  15627958