Вопросы с тегом «graph-algorithms»

16
Графовые задачи, NP-полные на ориентированных графах, но полиномиальные на неориентированных графах

Я ищу проблемы, которые, как известно, являются NPC для ориентированных графов, но имеют полиномиальный алгоритм для неориентированных графов. Я видел вопрос, касающийся здесь «направленных» проблем, которые проще, чем их «ненаправленный» вариант , но я ищу жесткость на направленной стороне....

16
Как называется этот тип задачи ориентированного графа?

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

16
Какова сложность этой проблемы графа?

Для простого неориентированного графа GGG найдите подмножество A≠∅A≠∅A\neq \emptyset вершин, такое что для любой вершины хотя бы половина соседей также находится в , иx∈Ax∈Ax\in AxxxAAA размер AAA минимален. То есть мы ищем кластер, в котором по крайней мере половина окрестности каждой внутренней...

16
Ссылка на алгоритм тестирования ацикличности смешанного графа?

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

15
Супер Марио течет в НП?

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

15
Известна ли эта плотная версия алгоритма Крускала?

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

15
Графовые разложения для объединения «локальных» функций маркировки вершин

ΣИксΠi j ∈ Eе( хя, хJ)∑x∏ij∈Ef(xi,xj)\sum_x \prod_{ij \in E} f(x_i,x_j)МаксимумИксΠi j ∈ Eе( хя, хJ)maxx∏ij∈Ef(xi,xj)\max_x \prod_{ij \in E} f(x_i,x_j) Где max или сумма берется по всем меткам VVV , произведение берется по всем ребрам ЕEE для графа G = { V, E}G={V,E}G=\{V,E\} а еff - произвольная...

15
2FA заявите о сложности k-Clique?

В простой форме: Может ли двусторонний конечный автомат распознавать вершинные графы, содержащие треугольник с состояниями?vvvo(v3)o(v3)o(v^3) Детали Здесь представляют интерес графы с вершинами, закодированные с использованием последовательности ребер, причем каждое ребро представляет собой пару...

15
Модульная декомпозиция и клик-ширина

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

15
Имея 4-циклический свободный граф

Проблема цикла заключается в следующем:Кkk Экземпляр: неориентированный граф с n вершинами и до ( nграммGGNnn края.( н2)(n2)n \choose 2 Вопрос: существует ли (правильный) цикл в G ?КkkграммGG Предыстория: для любого фиксированного мы можем решить цикл за времени.2 k O ( n 2 )Кkk2 к2k2kO (...

15
Рекомендации по модульной декомпозиции

Что такое хорошие статьи / книги, чтобы лучше понять силу модульного разложения и его свойства? Я особенно заинтересован в алгоритмических аспектах модульной декомпозиции. Я слышал, что можно найти модульную декомпозицию графа за линейное время. Есть ли относительно простой алгоритм для этого? А...

14
Обобщение венгерского алгоритма на общие неориентированные графы?

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

14
Точный алгоритм для задачи маркировки ребер в DAG

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

14
Количество срезов графа без использования алгоритма Каргера

Мы знаем, что алгоритм mincut Каргера может быть использован, чтобы доказать (неконструктивно), что максимальное число возможных срезов, которые может иметь граф, равно (n2)(n2)n \choose 2 . Мне было интересно, можем ли мы как-то доказать эту идентичность, дав биективное (довольно инъективное)...

14
Теоретические гарантии времени выполнения методов распространения убеждений?

Было доказано, что распространение убеждений является очень мощным методом исследования вероятностных графических моделей. Однако я ничего не знаю о BP, сравнимом с методами MCMC, где у нас могут быть полностью полиномиальные схемы рандомизированной аппроксимации (FPRAS) для # P-полных задач. Может...

14
Является ли проблема самой длинной трассы легче, чем проблема самой длинной трассы?

Самая длинная проблема на пути - NP-сложная. (Типичное?) Доказательство опирается на редукцию задачи о гамильтоновом пути (которая является NP-полной). Обратите внимание, что здесь путь считается простым (node-). То есть ни одна вершина не может встречаться более одного раза в пути. Очевидно, что...

14
Точные алгоритмы для r-доминирующего множества на графах ограниченной ширины

Учитывая график, , я хочу , чтобы найти оптимальный г -domination для G . То есть, я хочу подмножество S из V таким образом, что все вершины в G находятся на расстоянии не более чем г от некоторой вершины в S , при сведении к минимуму размера S .G=(V,E)G=(V,E)G = (V, E)rrrGGGSSSVVVGGGrrrSSSSSS Из...

14
Существование планарного расстояния?

Пусть G будет ненаправленным графом из n узлов, и пусть T будет подмножеством узлов V (G), называемых терминалами . Сохранитель расстояния (G, T) - это граф H, удовлетворяющий свойству dЧАС( u , v ) = dграмм( ты , ты )dЧАС(U,v)знак равноdграмм(U,v)d_H(u,v) = d_G(u,v) для всех узлов u, v в T....

14
Добавьте соответствие к гамильтонову пути, чтобы уменьшить максимальное расстояние между заданными парами вершин

Какова сложность следующей проблемы? Вход : гамильтонов путьв К пHHHKnКNK_n R⊆[n]2р⊆[N]2R \subseteq [n]^2 подмножество пар вершин положительное целое число kКk Запрос : существует ли сопоставление MMM такое, что для каждого (v,u)∈R(v,U)∈р(v,u) \in R , dG(v,u)≤kdграмм(v,U)≤Кd_G(v,u) \leq k ? (где...

13
Нахождение кратчайшего пути при наличии отрицательных циклов

Для ориентированного циклического графа, где вес каждого ребра может быть отрицательным, концепция «кратчайшего пути» имеет смысл, только если нет отрицательных циклов, и в этом случае вы можете применить алгоритм Беллмана-Форда. Тем не менее, я заинтересован в поиске кратчайшего пути между двумя...