Номер пересечения (теория графов)

В математической области теории графов число пересечений графа $G=(V,E)$ — наименьшее количество элементов в представлении $G$ как граф пересечений конечных множеств . В таком представлении каждая вершина представляется как множество, и две вершины соединяются ребром, если их множества имеют общий элемент. Аналогично, число пересечений — это наименьшее количество клик, необходимое для покрытия всех ребер. $G$ . ^{[ 1 ]}^{[ 2 ]}

Множество клик, покрывающих все ребра графа, называется покрытием ребер клики. ^{[ 3 ]} или край клик-обложки , ^{[ 4 ]} или даже просто кликовое покрытие , хотя последний термин неоднозначен: кликовое покрытие также может представлять собой набор клик, покрывающих все вершины графа. ^{[ 5 ]} Иногда вместо слова «покрытие» используется слово «покрытие». ^{[ 6 ]} Минимальное количество этих кликов не только называется числом пересечения, но и называется R -контентом . ^{[ 7 ]} крайний номер обложки клики , ^{[ 4 ]} или номер обложки клики . ^{[ 8 ]} Задача вычисления числа пересечений получила название проблемы числа пересечений . ^{[ 9 ]} пересечений базисная задача графа , ^{[ 10 ]} покрытие кликами , ^{[ 10 ]} клики проблема покрытия краевой , ^{[ 9 ]} и проблема конфликта ключевых слов . ^{[ 2 ]}

Каждый график с $n$ вершины и $m$ ребра имеют не более числа пересечений $\min(m,n^{2}/4)$ . Число пересечений NP-трудно вычислить или аппроксимировать, но можно решить с помощью фиксированных параметров .

Определения

Графики пересечений

Позволять ${\mathcal {F}}$ быть любым семейством множеств , допускающим множества в ${\mathcal {F}}$ чтобы повториться. Тогда пересечений граф ${\mathcal {F}}$ неориентированный граф , в котором есть вершина для каждого множества в ${\mathcal {F}}$ и ребро между каждыми двумя множествами, имеющими непустое пересечение. Таким образом, каждый граф можно представить в виде графа пересечений. ^{[ 11 ]} Число пересечения графа – это наименьшее число $k$ такая, что существует представление этого типа, для которого объединение множеств в ${\mathcal {F}}$ имеет $k$ элементы. ^{[ 1 ]} Проблема нахождения представления пересечения графа с заданным числом элементов известна как задача базиса графа пересечений . ^{[ 10 ]}

Накладки на края клика

Альтернативное определение числа пересечений графа $G$ заключается в том, что это наименьшее число клик в $G$ ( полные подграфы $G$ ), которые вместе покрывают все края $G$ . ^{[ 1 ]}^{[ 12 ]} Набор клик с этим свойством известен как покрытие ребер клики или покрытие реберной клики , и по этой причине число пересечений также иногда называют числом покрытия реберной клики . ^{[ 4 ]}

Эквивалентность

Равенство числа пересечений и числа покрытий реберной клики доказывается несложно. Предположим, что в одном направлении $G$ это граф пересечений семейства ${\mathcal {F}}$ множеств, объединение которых $U$ имеет $k$ элементы. Тогда для любого элемента $x\in U$ , подмножество вершин $G$ соответствующие множествам, содержащим $x$ образует клику: любые две вершины в этом подмножестве смежны, так как их множества имеют непустое пересечение, содержащее $x$ . Далее, каждое ребро в $G$ содержится в одной из этих клик: если ребро происходит из непустого пересечения множеств, содержащих элемент $y$ , то это ребро содержится в клике для $y$ . Поэтому края $G$ может быть покрыто $k$ клики, по одной на элемент $U$ . ^{[ 12 ]}

В обратном направлении, если график $G$ может быть покрыто $k$ клики, то каждая вершина $v$ из $G$ может быть представлено подмножеством клик, содержащих вершину $v$ . Два из этих подмножеств для двух вершин $u$ и $v$ , имеют непустое пересечение тогда и только тогда, когда в пересечении существует клика, содержащая их обоих, тогда и только тогда, когда существует ребро $uv$ включены в одну из покрывающих клик. ^{[ 12 ]}

Приложения

Представление графа как абстрактного графа пересечений множеств можно использовать для построения более конкретных геометрических представлений пересечений того же графа. В частности, если граф имеет номер пересечения $k$ , его можно представить в виде графа пересечений $k$ -мерная единичная гиперсфера (ее сферичность не более $k$ ). ^{[ 4 ]}^{[ 13 ]}

Покрытие клики можно использовать как своего рода схему разметки смежности для графа, в которой каждую вершину помечают двоичным значением с битом для каждой клики: нулем, если она не принадлежит клике, и единицей, если она принадлежит. Тогда две вершины являются смежными тогда и только тогда, когда побитовая а их меток не равна нулю. Длина меток — это номер пересечения графа. Этот метод использовался Э. Келлерманом из IBM в одном из первых применений чисел пересечения для маркировки набора ключевых слов, чтобы можно было быстро обнаружить конфликтующие ключевые слова. По этой причине другое название проблемы вычисления чисел пересечений — проблема конфликта ключевых слов . ^{[ 14 ]}^{[ 15 ]} Аналогично, в вычислительной геометрии представления, основанные на числе пересечений, рассматривались как компактное представление графов видимости , но существуют геометрические входные данные, для которых это представление требует почти квадратичного числа клик. ^{[ 16 ]}

Другой класс приложений возникает из-за проблем планирования , в которых несколько пользователей общего ресурса должны быть запланированы на определенные временные интервалы таким образом, чтобы несовместимые запросы никогда не планировались на один и тот же временной интервал, а все пары совместимых запросов выполнялись хотя бы один раз. слот вместе. Число пересечений графика совместимости дает минимальное количество временных интервалов, необходимых для такого расписания. ^{[ 2 ]} При разработке компиляторов для компьютеров с очень длинными командными словами можно использовать небольшое кликовое покрытие графа несовместимых операций для представления их несовместимости с помощью небольшого количества искусственных ресурсов, что позволяет использовать методы планирования на основе ресурсов для назначения операций слоты для инструкций. ^{[ 17 ]}

Шепард и Ветта отмечают, что число пересечений любой сети равно минимальному количеству ограничений, необходимых для в целочисленном программировании формулировки задачи вычисления максимального числа независимых множеств , в которой на каждую вершину приходится переменная 0–1 и ограничение, которое в каждой клике клики покрывают сумму переменных не более единицы. Они утверждают, что для графов пересечений путей в некоторых оптоволоконных сетях связи эти числа пересечений невелики, что объясняет относительную простоту решения определенных задач оптимизации при распределении полосы пропускания в сетях. ^{[ 3 ]}

В статистике и визуализации данных краевые клики графа, представляющие статистически неразличимые пары переменных, используются для создания компактных буквенных отображений , которые помогают визуализировать множественные парные сравнения, путем назначения буквы или другого визуального маркера для каждой клики и использования их для обеспечения графическое представление того, какие переменные неразличимы. ^{[ 18 ]}^{[ 19 ]}

При анализе пищевых сетей, описывающих отношения хищник-жертва между видами животных, граф конкуренции или граф перекрытия ниш представляет собой неориентированный граф, вершины которого представляют виды, а ребра представляют пары видов, которые оба конкурируют за одну и ту же добычу. Их можно получить из направленного ациклического графа, представляющего отношения хищник-жертва, нарисовав ребро. $u-v$ в графе конкуренции всякий раз, когда существует вид добычи $w$ такой, что граф отношений хищник-жертва имеет ребра $u\to w$ и $v\to w$ . Каждый граф конкуренции должен иметь хотя бы одну изолированную вершину , а число конкуренции произвольного графа представляет собой наименьшее количество изолированных вершин, которые можно добавить, чтобы превратить его в граф конкуренции. С биологической точки зрения, если наблюдается часть графа конкуренции, то число конкуренции представляет собой наименьшее возможное количество ненаблюдаемых видов добычи, необходимое для ее объяснения. Число конкуренции не более чем равно числу пересечений: любой неориентированный граф можно преобразовать в граф конкуренции, добавив вид добычи для каждой клики в покрытие реберной клики. Однако это соотношение неточно, поскольку виды-хищники также могут стать добычей других видов. На графике с $n$ вершины, не более $n-2$ из них могут быть добычей более чем одного другого вида, поэтому число конкуренции равно как минимум числу пересечений минус $n-2$ . ^{[ 20 ]}

Покрытия краевой клики также использовались для вывода о существовании белковых комплексов , систем взаимно взаимодействующих белков, на основе сетей белок-белкового взаимодействия, описывающих только парные взаимодействия между белками. ^{[ 21 ]} В более общем плане Гийом и Латапи утверждали, что для сложных сетей всех типов замена сети двудольным графом, соединяющим его вершины с кликами в покрытии клик, подчеркивает структуру сети. ^{[ 22 ]}

Верхние границы

Тривиально, граф с $m$ ребра имеют не более числа пересечений $m$ . Каждое ребро само по себе является двухвершинной кликой. Есть $m$ этих клик и вместе они покрывают все края. ^{[ 23 ]} Верно также, что каждый граф с $n$ вершины имеют не более чем число пересечений $\lfloor n^{2}/4\rfloor$ . Более того, края каждого $n$ -вершинный граф может быть покрыт не более чем $\lfloor n^{2}/4\rfloor$ клики, каждая из которых представляет собой либо одно ребро, либо треугольник. Алгоритм нахождения этого покрытия прост: удалить любые две соседние вершины и индуктивно покрыть оставшийся граф. Восстановив две удаленные вершины, покройте ребра их общих соседей треугольниками, оставив ребра необщих соседей как клики из двух вершин. Индуктивная крышка имеет не более $\lfloor (n-2)^{2}/4\rfloor$ клик, а две удаленные вершины дают не более $n-1$ клики, максимальные, когда все остальные вершины являются неразделенными соседями и ребро между двумя вершинами должно использоваться как клика. Сложение этих двух величин дает $\lfloor n^{2}/4\rfloor$ сплошные клики. ^{[ 2 ]}^{[ 12 ]} Это обобщает теорему Мантеля о том, что граф без треугольников имеет не более $\lfloor n^{2}/4\rfloor$ ребер, поскольку в графе без треугольников единственное оптимальное покрытие ребер клики имеет одну клику на ребро, и, следовательно, число пересечений равно количеству ребер. ^{[ 2 ]}

Еще более жесткая граница возможна, когда число ребер строго больше, чем ${\tfrac {n^{2}}{4}}$ . Позволять $p$ — количество пар вершин, не соединенных ребром в данном графе $G$ , и пусть $t$ быть уникальным целым числом, для которого $(t-1)t\leq p<t(t+1)$ . Тогда число пересечений $G$ самое большее $p+t$ . ^{[ 2 ]}^{[ 24 ]} Графы, являющиеся дополнением имеют разреженного графа, небольшие числа пересечений: число пересечений любого $n$ -вершинный граф $G$ самое большее $2e^{2}(d+1)^{2}\ln n$ , где $e$ является основанием натурального логарифма и $d$ - максимальная степень графа дополнения $G$ . ^{[ 6 ]}

Из глубоких результатов о структуре графов без клешней следует , что при связном $n$ -вершинный граф без клешней имеет не менее трёх независимых вершин, число пересечений не более $n$ . Остается нерешенной проблема, справедливо ли это для всех графов без клешней, не требуя от них наличия больших независимых множеств. ^{[ 8 ]} Важным подклассом графов без клешней являются линейные графы , графы, представляющие ребра и соприкасающиеся пары ребер какого-либо другого графа. $G$ . Оптимальное кликовое покрытие линейного графа $L(G)$ может быть образовано одной кликой для каждого треугольника в $G$ который имеет две или три вершины степени 2 и одну клику для каждой вершины, которая имеет степень не ниже двух и не является вершиной второй степени ни одного из этих треугольников. Число пересечений — это количество клик этих двух типов. ^{[ 7 ]}

В –Реньи–Гилберта Эрдеша модели случайных графов , в которой все графы на $n$ помеченные вершины одинаково вероятны (или, что то же самое, каждое ребро присутствует или отсутствует независимо от других ребер с вероятностью ${\tfrac {1}{2}}$ ) номер пересечения $n$ -вершинный случайный граф с высокой вероятностью $\Theta \left({\frac {n^{2}}{\log ^{2}n}}\right),$ меньше в раз $\log ^{2}n$ чем количество ребер. В этих графах максимальные клики имеют (с высокой вероятностью) только логарифмическое количество вершин, а это означает, что именно столько их необходимо, чтобы покрыть все ребра. Сложная часть оценки состоит в том, чтобы доказать, что можно найти достаточное количество клик логарифмического размера, чтобы покрыть множество ребер, позволяя покрыть оставшиеся оставшиеся ребра кликами с двумя вершинами. ^{[ 25 ]}^{[ 26 ]}

Большая часть ранних исследований чисел пересечений включала вычисление этих чисел на различных конкретных графах, например, графах, образованных удалением полного подграфа или идеальным паросочетанием из более крупного полного графа. ^{[ 27 ]}

Вычислительная сложность

Проверка того, является ли данный граф $G$ имеет номер пересечения не более заданного числа $k$ является NP-полной . ^{[ 10 ]}^{[ 7 ]}^{[ 15 ]} Следовательно, вычислить число пересечений данного графа также NP-трудно. В свою очередь, сложность числа пересечений была использована для доказательства NP-полноты распознавания квадратов разбитых графов . ^{[ 28 ]}

Однако проблема вычисления числа пересечений является решаемой с фиксированным параметром : то есть ее можно решить за время, ограниченное полиномом от $n$ умноженный на большую, но вычислимую функцию числа пересечений $k$ . ^{[ 5 ]}^{[ 29 ]} Это можно показать, заметив, что существует не более $2^{k}$ различные замкнутые окрестности в графе (две вершины, принадлежащие одному набору клик, имеют одну и ту же окрестность) и что граф, сформированный путем выбора одной вершины на каждую замкнутую окрестность, имеет то же число пересечений, что и исходный граф. ^{[ 5 ]}^{[ 30 ]} Следовательно, за полиномиальное время входные данные можно свести к меньшему ядру с не более чем ${\textstyle 2^{k}}$ вершины и $O(4^{k})$ края. Применение с экспоненциальным временем процедуры поиска динамического программирования над подмножествами ребер этого ядра дает время $2^{O(4^{k})}+n^{O(1)}$ , двойная экспонента в $k$ . ^{[ 5 ]}^{[ 29 ]} Двойная экспоненциальная зависимость от $k$ не может быть сведено к одной экспоненте с помощью кернеризации полиномиального размера, если только полиномиальная иерархия не рухнет, ^{[ 31 ]} и если гипотеза экспоненциального времени верна, то необходима двойная экспоненциальная зависимость независимо от того, используется ли кернеризация. ^{[ 29 ]} На графах с ограниченной шириной дерева динамическое программирование древовидного разложения графа может найти число пересечений за линейное время, ^{[ 32 ]}^{[ 21 ]} но более простые алгоритмы, основанные на конечных наборах правил редукции, не работают. ^{[ 32 ]}

Задача не может быть аппроксимирована за полиномиальное время с коэффициентом аппроксимации лучше, чем $n^{c}$ , для некоторой константы $c$ , ^{[ 33 ]} и наилучший известный коэффициент аппроксимации лучше, чем тривиальный $O(n^{2})$ только полилогарифмическим коэффициентом. ^{[ 5 ]} Исследователи в этой области также исследовали вычислительную эффективность эвристик без гарантий качества получаемых ими решений и их поведения в реальных сетях. ^{[ 5 ]}^{[ 34 ]}

Для некоторых специальных классов графов известны более эффективные алгоритмы. Число пересечений интервального графа всегда равно числу его максимальных клик , которые можно вычислить за полиномиальное время. ^{[ 35 ]}^{[ 36 ]} В более общем смысле, в хордальных графах число пересечений может быть вычислено с помощью алгоритма, который рассматривает вершины в порядке исключения графа (порядок, в котором каждая вершина и ее последующие соседи образуют клику) и который для каждой вершины $v$ , образует клику для $v$ и его последующих соседей всякий раз, когда хотя бы одно из ребер, инцидентных $v$ не покрыта какой-либо более ранней кликой. ^{[ 36 ]} Также возможно найти число пересечений за линейное время на графах дуг окружности . ^{[ 37 ]} Однако, хотя эти графы имеют только полиномиальное количество клик для выбора покрытия, одного лишь небольшого количества клик недостаточно, чтобы упростить задачу: существуют семейства графов с полиномиальным числом клик, для которых число пересечений остается NP-трудным. . ^{[ 9 ]} Число пересечений также можно найти за полиномиальное время для графов, максимальная степень которых равна пяти, но является NP-трудным для графов максимальной степени шесть. ^{[ 38 ]}^{[ 39 ]} На планарных графах точное вычисление числа пересечений остается NP-сложным, но оно имеет схему аппроксимации за полиномиальное время, основанную на методе Бейкера . ^{[ 21 ]}

См. также

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

Ссылки

^ Jump up to: ^а ^б ^с Гросс, Джонатан Л.; Йеллен, Джей (2006), Теория графов и ее приложения , CRC Press, стр. 440, ISBN 978-1-58488-505-4
^ Jump up to: ^а ^б ^с ^д ^и ^ж Робертс, Фред С. (1985), «Применение покрытий ребер кликами», Discrete Applied Mathematics , 10 (1): 93–109, doi : 10.1016/0166-218X(85)90061-7 , MR 0770871
^ Jump up to: ^а ^б Шеперд, ФБ; Ветта, А. (ноябрь 2004 г.), «Осветительные волокна в темной сети» , Журнал IEEE по выбранным областям связи , 22 (9): 1583–1588, doi : 10.1109/jsac.2004.833850 , S2CID 31868129
^ Jump up to: ^а ^б ^с ^д Майкл, ТС; Квинт, Томас (2006), «Сферичность, кубичность и рёберные кликовые покрытия графов», Discrete Applied Mathematics , 154 (8): 1309–1313, doi : 10.1016/j.dam.2006.01.004
^ Jump up to: ^а ^б ^с ^д ^и ^ж Грамм, Йенс; Го, Цзюн; Хюффнер, Фальк; Нидермейер, Рольф (2009), «Сокращение данных и точные алгоритмы покрытия клик» (PDF) , Journal of Experimental Algorithmics , 13 (2): 2–15, doi : 10.1145/1412228.1412236 , S2CID 15057639
^ Jump up to: ^а ^б Алон, Нога (1986), «Покрытие графов минимальным числом отношений эквивалентности» (PDF) , Combinatorica , 6 (3): 201–206, doi : 10.1007/bf02579381 , S2CID 13522339
^ Jump up to: ^а ^б ^с Орлин, Дж. (1977), «Удовлетворенность в теории графов: покрытие графов кликами», Indagationes Mathematicae , 80 (5): 406–424, doi : 10.1016/1385-7258(77)90055-5
^ Jump up to: ^а ^б Джавади, Рамин; Хаджеби, Сепер (2019), «Покрытие графов без когтей граничной кликой», Journal of Graph Theory , 90 (3): 311–405, arXiv : 1608.07723 , doi : 10.1002/jgt.22403 , MR 3904838 , S2CID 67770018
^ Jump up to: ^а ^б ^с Розген, Билл; Стюарт, Лорна (2007), «Результаты по сложности на графах с небольшим количеством клик» , Discrete Mathematics & Theoretical Computer Science , 9 (1): 127–135, doi : 10.46298/dmtcs.387 , MR 2335890
^ Jump up to: ^а ^б ^с ^д Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , Серия книг по математическим наукам (1-е изд.), Нью-Йорк: WH Freeman and Company , ISBN 9780716710455 , MR 0519066 , OCLC 247570676 , Задачи GT17 (покрытие кликами) и GT59 (базис графа пересечений)
^ Шпильрайн-Марчевский, Эдвард (1945), «Sur deux proprietés desclassd'ensembles», Основы математики (на французском языке), 33 : 303–307, doi : 10.4064/fm-33-1-303-307 , MR 0015448
^ Jump up to: ^а ^б ^с ^д Эрдеш, Пол ; Гудман, AW; Поса, Луи (1966), Представление графа посредством пересечений множеств» (PDF) , Canadian Journal of Mathematics , 18 (1) CiteSeerX 106–112 , : « 014-3 , MR 0186575 , S2CID
^ Майкл, ТС; Квинт, Томас (2009), Опечатка: сферичность, кубичность и рёберные кликовые покрытия графов.
^ Келлерман, Э. (1973), «Определение конфликта ключевых слов», Бюллетень технической информации IBM , 16 (2): 544–546 , цитируется Коу, Стокмейером и Вонгом (1978).
^ Jump up to: ^а ^б Коу, LT; Стокмейер, LJ ; Вонг, К.К. (1978), «Покрытие ребер кликами с учетом конфликтов ключевых слов и графов пересечений», Communications of the ACM , 21 (2): 135–139, doi : 10.1145/359340.359346 , S2CID 15059696
^ Агарвал, ПК ; Алон, Н. ; Аронов, Б. ; Сури, С. (1994), «Можно ли представить графы видимости компактно?», Discrete & Computational Geometry , 12 (3): 347–365, doi : 10.1007/BF02574385 , MR 1298916
^ Раджагопалан, Субраманиан; Вачхараджани, Маниш; Малик, Шарад (2000), «Обработка нерегулярной ILP в обычных планировщиках VLIW с использованием искусственных ограничений ресурсов», Материалы Международной конференции 2000 года по компиляторам, архитектурам и синтезу для встраиваемых систем, CASES 2000, Сан-Хосе, Калифорния, США, 7 ноября – 18, 2000 г. , Ассоциация вычислительной техники, стр. 157–164, doi : 10.1145/354880.354902 , ISBN 1-58113-338-3 , S2CID 6498253
^ Пьефо, Ханс-Петер (2004), «Алгоритм буквенного представления всех парных сравнений», Журнал вычислительной и графической статистики , 13 (2): 456–466, doi : 10.1198/1061860043515 , MR 2063995 , S2CID 122068627
^ Грамм, Йенс; Го, Цзюн; Хюффнер, Фальк; Нидермайер, Рольф; Пьефо, Ханс-Петер; Шмид, Рамона (2008), «Алгоритмы для компактного отображения букв: сравнение и оценка», Вычислительная статистика и анализ данных , 52 (2): 725–736, doi : 10.1016/j.csda.2006.09.035 , MR 2418523
^ Опсут, Роберт Дж. (1982), «О вычислении числа конкуренции графа», SIAM Journal on Algebraic and Discrete Methods , 3 (4): 420–428, doi : 10.1137/0603043 , MR 0679638
^ Jump up to: ^а ^б ^с Бланшетт, Матье; Ким, Итан; Ветта, Адриан (2012), «Покрытие кликами в разреженных сетях», Бадер, Дэвид А.; Мутцель, Петра (ред.), Труды 14-го совещания по разработке алгоритмов и экспериментам, ALENEX 2012, The Westin Miyako, Киото, Япония, 16 января 2012 г. , Общество промышленной и прикладной математики, стр. 93–102, doi : 10.1137/1.9781611972924.10 , ISBN 978-1-61197-212-2
^ Гийом, Жан-Лу; Латапи, Матье (2004), «Двухчастная структура всех сложных сетей» (PDF) , Information Processing Letters , 90 (5): 215–221, doi : 10.1016/j.ipl.2004.03.007 , MR 2054656 , S2CID 6254096
^ Балакришнан, В.К. (1997), Очерк теории и проблемы теории графов Шаума , McGraw-Hill Professional, стр. 40, ISBN 978-0-07-005489-9
^ Ловас, Л. (1968), «О покрытии графов», Эрдеш, П .; Катона Г. (ред.), Материалы коллоквиума, состоявшегося в Тихани, Венгрия, 1966 г. , Academic Press, стр. 231–236 ; по словам Робертса (1985)
^ БОЛОБАС, Бела ; Эрдеш, Пол ; Спенсер, Джоэл ; Уэст, Дуглас Б. (1993), «Кликовые покрытия ребер случайного графа» (PDF) , Combinatorica , 13 (1): 1–5, doi : 10.1007/BF01202786 , MR 1221173 , S2CID 26565829
^ Фриз, Алан ; Рид, Брюс (1995), «Покрытие ребер случайного графа кликами», Combinatorica , 15 (4): 489–497, arXiv : 1103.4870 , doi : 10.1007/BF01192522 , MR 1364022 , S2CID 7326662
^ Пуллман, Норман Дж. (1983), «Кликовые покрытия графов - обзор», в Рейнольдсе, Луи; Касс, Антуан (ред.), Комбинаторная математика X: Материалы конференции, состоявшейся в Аделаиде, Австралия, 23-27 августа 1982 г. , Конспекты лекций по математике, том. 1036, Springer, стр. 72–85, doi : 10.1007/bfb0071509 , ISBN. 978-3-540-12708-6 , МР 0731572
^ Лау, Лап Чи; Корнейл, Дерек Г. (2004), «Распознавание степеней правильных интервальных, расщепленных и хордальных графов», SIAM Journal on Discrete Mathematics , 18 (1): 83–102, doi : 10.1137/S0895480103425930 , MR 2112490
^ Jump up to: ^а ^б ^с Циган, Марек; Пилипчук, Марцин; Пилипчук, Михал (2016), «Известные алгоритмы покрытия реберной клики, вероятно, оптимальны», SIAM Journal on Computing , 45 (1): 67–83, arXiv : 1203.1754 , doi : 10.1137/130947076 , MR 3448348 , S2CID 11264145
^ Дьярфас, А. (1990), «Простая нижняя оценка покрытий ребер кликами», Discrete Mathematics , 85 (1): 103–104, doi : 10.1016/0012-365X(90)90168-H , MR 1078317
^ Гиган, Марек; Крач, Стефан; Пилипчук, Марцин; Пилипчук, Михал; Вальстрём, Магнус (2014), «Кликовое покрытие и разделение графов: новые результаты о несжимаемости» (PDF) , Транзакции ACM по теории вычислений 6 ( 2): 6:1–6:19, doi : 10.1145/2594439 , S287ID876 ,
^ Jump up to: ^а ^б Бодлендер, Ханс Л .; ван Антверпен-де Флюитер, Бабетта (2001), «Алгоритмы сокращения для графов малой ширины дерева», Information and Computation , 167 (2): 86–119, doi : 10.1006/inco.2000.2958 , MR 1835592
^ Лунд, Карстен ; Яннакакис, Михалис (1994), «О сложности аппроксимации задач минимизации», Журнал ACM , 41 (5): 960–981, doi : 10.1145/185675.306789 , MR 1371491
^ Конте, Алессио; Гросси, Роберто; Марино, Андреа (2020), «Крупномасштабное кликовое покрытие реальных сетей», Information and Computation , 270 , статья 104464, 15pp, doi : 10.1016/j.ic.2019.104464 , hdl : 11568/1028251 , MR 4050008 , S2CID 203036455
^ Опсут, Р.Дж.; Робертс, Ф.С. (1981), «Об обслуживании автопарка, мобильных радиочастотах, назначении задач и проблемах поэтапного движения», в Чартране, Г .; Алави, Ю. ; Голдсмит, ДЛ; Лесняк-Фостер, Л.; Лик, доктор медицинских наук (ред.), Труды 4-й Международной конференции по теории и приложениям графов, Университет Западного Мичигана, Каламазу, Мичиган, 6–9 мая 1980 г. , Нью-Йорк: Wiley, стр. 479–492, MR 0634549. ; по словам Робертса (1985)
^ Jump up to: ^а ^б Шайнерман, Эдвард Р .; Тренк, Энн Н. (1999), «О дробном числе пересечения графа», Graphs and Combinatorics , 15 (3): 341–351, doi : 10.1007/s003730050068 , MR 1723018 , S2CID 33081703
^ Сюй, Вэнь Лянь; Цай, Куо-Хуэй (1991), «Алгоритмы линейного времени на дуговых графах», Information Processing Letters , 40 (3): 123–129, doi : 10.1016/0020-0190(91)90165-E , MR 1143909
^ Пуллман, Норман Дж. (1984), «Кликовое покрытие графов, IV: Алгоритмы», SIAM Journal on Computing , 13 (1): 57–75, doi : 10.1137/0213005 , MR 0731027
^ Гувер, Д. Н. (1992), «Сложность задач покрытия графов для графов низкой степени», Журнал комбинаторной математики и комбинаторных вычислений , 11 : 187–208, MR 1160076

Внешние ссылки

Вайсштейн, Эрик В. , «Номер пересечения» , MathWorld

[gy06-1] Jump up to: ^а ^б ^с Гросс, Джонатан Л.; Йеллен, Джей (2006), Теория графов и ее приложения , CRC Press, стр. 440, ISBN 978-1-58488-505-4

[r85-2] Jump up to: ^а ^б ^с ^д ^и ^ж Робертс, Фред С. (1985), «Применение покрытий ребер кликами», Discrete Applied Mathematics , 10 (1): 93–109, doi : 10.1016/0166-218X(85)90061-7 , MR 0770871

[sv04-3] Jump up to: ^а ^б Шеперд, ФБ; Ветта, А. (ноябрь 2004 г.), «Осветительные волокна в темной сети» , Журнал IEEE по выбранным областям связи , 22 (9): 1583–1588, doi : 10.1109/jsac.2004.833850 , S2CID 31868129

[mtq06-4] Jump up to: ^а ^б ^с ^д Майкл, ТС; Квинт, Томас (2006), «Сферичность, кубичность и рёберные кликовые покрытия графов», Discrete Applied Mathematics , 154 (8): 1309–1313, doi : 10.1016/j.dam.2006.01.004

[gghn09-5] Jump up to: ^а ^б ^с ^д ^и ^ж Грамм, Йенс; Го, Цзюн; Хюффнер, Фальк; Нидермейер, Рольф (2009), «Сокращение данных и точные алгоритмы покрытия клик» (PDF) , Journal of Experimental Algorithmics , 13 (2): 2–15, doi : 10.1145/1412228.1412236 , S2CID 15057639

[a86-6] Jump up to: ^а ^б Алон, Нога (1986), «Покрытие графов минимальным числом отношений эквивалентности» (PDF) , Combinatorica , 6 (3): 201–206, doi : 10.1007/bf02579381 , S2CID 13522339

[o77-7] Jump up to: ^а ^б ^с Орлин, Дж. (1977), «Удовлетворенность в теории графов: покрытие графов кликами», Indagationes Mathematicae , 80 (5): 406–424, doi : 10.1016/1385-7258(77)90055-5

[jh19-8] Jump up to: ^а ^б Джавади, Рамин; Хаджеби, Сепер (2019), «Покрытие графов без когтей граничной кликой», Journal of Graph Theory , 90 (3): 311–405, arXiv : 1608.07723 , doi : 10.1002/jgt.22403 , MR 3904838 , S2CID 67770018

[rs07-9] Jump up to: ^а ^б ^с Розген, Билл; Стюарт, Лорна (2007), «Результаты по сложности на графах с небольшим количеством клик» , Discrete Mathematics & Theoretical Computer Science , 9 (1): 127–135, doi : 10.46298/dmtcs.387 , MR 2335890

[gj79-10] Jump up to: ^а ^б ^с ^д Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , Серия книг по математическим наукам (1-е изд.), Нью-Йорк: WH Freeman and Company , ISBN 9780716710455 , MR 0519066 , OCLC 247570676 , Задачи GT17 (покрытие кликами) и GT59 (базис графа пересечений)

[sm45-11] Шпильрайн-Марчевский, Эдвард (1945), «Sur deux proprietés desclassd'ensembles», Основы математики (на французском языке), 33 : 303–307, doi : 10.4064/fm-33-1-303-307 , MR 0015448

[egp66-12] Jump up to: ^а ^б ^с ^д Эрдеш, Пол ; Гудман, AW; Поса, Луи (1966), Представление графа посредством пересечений множеств» (PDF) , Canadian Journal of Mathematics , 18 (1) CiteSeerX 106–112 , : « 014-3 , MR 0186575 , S2CID

[mtq09-13] Майкл, ТС; Квинт, Томас (2009), Опечатка: сферичность, кубичность и рёберные кликовые покрытия графов.

[k73-14] Келлерман, Э. (1973), «Определение конфликта ключевых слов», Бюллетень технической информации IBM , 16 (2): 544–546 , цитируется Коу, Стокмейером и Вонгом (1978).

[ksw78-15] Jump up to: ^а ^б Коу, LT; Стокмейер, LJ ; Вонг, К.К. (1978), «Покрытие ребер кликами с учетом конфликтов ключевых слов и графов пересечений», Communications of the ACM , 21 (2): 135–139, doi : 10.1145/359340.359346 , S2CID 15059696

[aaas94-16] Агарвал, ПК ; Алон, Н. ; Аронов, Б. ; Сури, С. (1994), «Можно ли представить графы видимости компактно?», Discrete & Computational Geometry , 12 (3): 347–365, doi : 10.1007/BF02574385 , MR 1298916

[rvm00-17] Раджагопалан, Субраманиан; Вачхараджани, Маниш; Малик, Шарад (2000), «Обработка нерегулярной ILP в обычных планировщиках VLIW с использованием искусственных ограничений ресурсов», Материалы Международной конференции 2000 года по компиляторам, архитектурам и синтезу для встраиваемых систем, CASES 2000, Сан-Хосе, Калифорния, США, 7 ноября – 18, 2000 г. , Ассоциация вычислительной техники, стр. 157–164, doi : 10.1145/354880.354902 , ISBN 1-58113-338-3 , S2CID 6498253

[p04-18] Пьефо, Ханс-Петер (2004), «Алгоритм буквенного представления всех парных сравнений», Журнал вычислительной и графической статистики , 13 (2): 456–466, doi : 10.1198/1061860043515 , MR 2063995 , S2CID 122068627

[gghnps08-19] Грамм, Йенс; Го, Цзюн; Хюффнер, Фальк; Нидермайер, Рольф; Пьефо, Ханс-Петер; Шмид, Рамона (2008), «Алгоритмы для компактного отображения букв: сравнение и оценка», Вычислительная статистика и анализ данных , 52 (2): 725–736, doi : 10.1016/j.csda.2006.09.035 , MR 2418523

[o82-20] Опсут, Роберт Дж. (1982), «О вычислении числа конкуренции графа», SIAM Journal on Algebraic and Discrete Methods , 3 (4): 420–428, doi : 10.1137/0603043 , MR 0679638

[bkv12-21] Jump up to: ^а ^б ^с Бланшетт, Матье; Ким, Итан; Ветта, Адриан (2012), «Покрытие кликами в разреженных сетях», Бадер, Дэвид А.; Мутцель, Петра (ред.), Труды 14-го совещания по разработке алгоритмов и экспериментам, ALENEX 2012, The Westin Miyako, Киото, Япония, 16 января 2012 г. , Общество промышленной и прикладной математики, стр. 93–102, doi : 10.1137/1.9781611972924.10 , ISBN 978-1-61197-212-2

[gl04-22] Гийом, Жан-Лу; Латапи, Матье (2004), «Двухчастная структура всех сложных сетей» (PDF) , Information Processing Letters , 90 (5): 215–221, doi : 10.1016/j.ipl.2004.03.007 , MR 2054656 , S2CID 6254096

[b97-23] Балакришнан, В.К. (1997), Очерк теории и проблемы теории графов Шаума , McGraw-Hill Professional, стр. 40, ISBN 978-0-07-005489-9

[l68-24] Ловас, Л. (1968), «О покрытии графов», Эрдеш, П .; Катона Г. (ред.), Материалы коллоквиума, состоявшегося в Тихани, Венгрия, 1966 г. , Academic Press, стр. 231–236 ; по словам Робертса (1985)

[besw93-25] БОЛОБАС, Бела ; Эрдеш, Пол ; Спенсер, Джоэл ; Уэст, Дуглас Б. (1993), «Кликовые покрытия ребер случайного графа» (PDF) , Combinatorica , 13 (1): 1–5, doi : 10.1007/BF01202786 , MR 1221173 , S2CID 26565829

[fr95-26] Фриз, Алан ; Рид, Брюс (1995), «Покрытие ребер случайного графа кликами», Combinatorica , 15 (4): 489–497, arXiv : 1103.4870 , doi : 10.1007/BF01192522 , MR 1364022 , S2CID 7326662

[p83-27] Пуллман, Норман Дж. (1983), «Кликовые покрытия графов - обзор», в Рейнольдсе, Луи; Касс, Антуан (ред.), Комбинаторная математика X: Материалы конференции, состоявшейся в Аделаиде, Австралия, 23-27 августа 1982 г. , Конспекты лекций по математике, том. 1036, Springer, стр. 72–85, doi : 10.1007/bfb0071509 , ISBN. 978-3-540-12708-6 , МР 0731572

[lc04-28] Лау, Лап Чи; Корнейл, Дерек Г. (2004), «Распознавание степеней правильных интервальных, расщепленных и хордальных графов», SIAM Journal on Discrete Mathematics , 18 (1): 83–102, doi : 10.1137/S0895480103425930 , MR 2112490

[cpp16-29] Jump up to: ^а ^б ^с Циган, Марек; Пилипчук, Марцин; Пилипчук, Михал (2016), «Известные алгоритмы покрытия реберной клики, вероятно, оптимальны», SIAM Journal on Computing , 45 (1): 67–83, arXiv : 1203.1754 , doi : 10.1137/130947076 , MR 3448348 , S2CID 11264145

[g90-30] Дьярфас, А. (1990), «Простая нижняя оценка покрытий ребер кликами», Discrete Mathematics , 85 (1): 103–104, doi : 10.1016/0012-365X(90)90168-H , MR 1078317

[ckppw14-31] Гиган, Марек; Крач, Стефан; Пилипчук, Марцин; Пилипчук, Михал; Вальстрём, Магнус (2014), «Кликовое покрытие и разделение графов: новые результаты о несжимаемости» (PDF) , Транзакции ACM по теории вычислений 6 ( 2): 6:1–6:19, doi : 10.1145/2594439 , S287ID876 ,

[bf01-32] Jump up to: ^а ^б Бодлендер, Ханс Л .; ван Антверпен-де Флюитер, Бабетта (2001), «Алгоритмы сокращения для графов малой ширины дерева», Information and Computation , 167 (2): 86–119, doi : 10.1006/inco.2000.2958 , MR 1835592

[ly94-33] Лунд, Карстен ; Яннакакис, Михалис (1994), «О сложности аппроксимации задач минимизации», Журнал ACM , 41 (5): 960–981, doi : 10.1145/185675.306789 , MR 1371491

[cgm20-34] Конте, Алессио; Гросси, Роберто; Марино, Андреа (2020), «Крупномасштабное кликовое покрытие реальных сетей», Information and Computation , 270 , статья 104464, 15pp, doi : 10.1016/j.ic.2019.104464 , hdl : 11568/1028251 , MR 4050008 , S2CID 203036455

[or81-35] Опсут, Р.Дж.; Робертс, Ф.С. (1981), «Об обслуживании автопарка, мобильных радиочастотах, назначении задач и проблемах поэтапного движения», в Чартране, Г .; Алави, Ю. ; Голдсмит, ДЛ; Лесняк-Фостер, Л.; Лик, доктор медицинских наук (ред.), Труды 4-й Международной конференции по теории и приложениям графов, Университет Западного Мичигана, Каламазу, Мичиган, 6–9 мая 1980 г. , Нью-Йорк: Wiley, стр. 479–492, MR 0634549. ; по словам Робертса (1985)

[st99-36] Jump up to: ^а ^б Шайнерман, Эдвард Р .; Тренк, Энн Н. (1999), «О дробном числе пересечения графа», Graphs and Combinatorics , 15 (3): 341–351, doi : 10.1007/s003730050068 , MR 1723018 , S2CID 33081703

[ht91-37] Сюй, Вэнь Лянь; Цай, Куо-Хуэй (1991), «Алгоритмы линейного времени на дуговых графах», Information Processing Letters , 40 (3): 123–129, doi : 10.1016/0020-0190(91)90165-E , MR 1143909

[p84-38] Пуллман, Норман Дж. (1984), «Кликовое покрытие графов, IV: Алгоритмы», SIAM Journal on Computing , 13 (1): 57–75, doi : 10.1137/0213005 , MR 0731027

[h92-39] Гувер, Д. Н. (1992), «Сложность задач покрытия графов для графов низкой степени», Журнал комбинаторной математики и комбинаторных вычислений , 11 : 187–208, MR 1160076

[ 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 ]