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

22
Приложения Vertex Cover в реальном мире

Какие приложения есть в Vertex Cover Problem в реальном мире? В каких отраслевых или исследовательских проектах используется фактически внедренное программное обеспечение, основанное на теоретических результатах для задачи Vertex Cover? В частности, реализованы ли какие-либо из следующих...

22
Нахождение вершин-близнецов в графах

Пусть G=(V,E)G=(V,E)G=(V,E) - граф. Для вершины x∈Vx∈Vx\in V , определим N(x)N(x)N(x) , чтобы быть (открытая) окрестность xxx в GGG . То есть N(x)={y∈V|{x,y}∈E}N(x)={y∈V|{x,y}∈E}N(x)=\{y\in V \,\vert\, \{x,y\}\in E\} . Определим две вершиныu,vu,vu,v вGGG какдвойники,еслиuuu иvvv имеют одинаковый...

21
Графы, в которых каждый минимальный разделитель является независимым множеством

Фон: Пусть две вершины неориентированного графа . Множество вершин является -сепаратором, если и принадлежат различным связным компонентам . Если собственное подмножество -сепаратора является -сепаратором, то является минимальным -сепаратором. Множество вершин является (минимальным) разделителем,...

21
Алгоритм Max-Cut, который не должен работать, непонятно почему

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

21
Эффективно найти 5-цикл в разреженном графе.

(вставлено из MathOverflow) Здравствуй, Я читал эту тему: /mathpro/16393/finding-a-cycle-of-fixed-length Я хочу найти 5-цикл в графике. На самом деле, то, что я действительно хочу, это кратчайший нечетный цикл длиной не менее 5, но, возможно, это немного не относится к делу. В моих целях я...

20
Сокращение использования пространства st-подключения с несколькими проходами?

Предположим, что граф с вершинами представлен как поток из ребер, но допускается несколько проходов по потоку.н мграммGGNnnмmm Моника Раух Хензингер, Прабхакар Рагхаван и Шридар Раджагопалан отметили, что пространство необходимо, чтобы определить, существует ли путь между двумя заданными вершинами...

20
Нужно ли называть матричное умножение раз, чтобы найти коготь

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

20
Детерминированный параллельный алгоритм для идеального сопоставления в общих графах?

В классе сложности есть некоторые проблемы, предположительно не входящие в класс N C , то есть проблемы с детерминированными параллельными алгоритмами. Проблема максимального потока является одним из примеров. И есть проблемы, СЧИТАЕМЫЕ быть в N C , но доказательство еще не...

20
Распознавание линейных графиков гиперграфов

Линейный граф гиперграфа - это (простой) граф G, имеющий ребра H, поскольку вершины с двумя ребрами H смежны в G, если они имеют непустое пересечение. Гиперграф является r- гиперграфом, если каждое из его ребер имеет не более r вершин.ЧАСHHграммGGЧАСHHЧАСHHграммGGрrrрrr Какова сложность следующей...

20
Как быстро мы можем вычислить набор включений в набор семейства?

Учитывая набор семейство FF\mathcal{F} подмножеств универсума UUU . Пусть S1,S2∈FS1,S2∈FS_1,S_2 \in \mathcal F и мы хотим ответить на это S1⊆S2S1⊆S2S_1 \subseteq S_2 . Я ищу структуру данных, которая позволит мне быстро ответить на это. Мое приложение из теории графов, где я хочу посмотреть,...

19
поддержание сбалансированного остовного дерева растущего неориентированного графа

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

19
Подсчитайте количество связующих деревьев быстро

t(G)t(G)t(G)GGGnnnt(G)t(G)t(G)O(n3)O(n3)O(n^3)QGJ11n2det(J+Q)1n2det(J+Q)\frac{1}{n^2} \det(J + Q)QQQGGGJJJ111 Интересно, есть ли способ вычислить t(G)t(G)t(G) быстрее. (Да, есть более быстрые, чем O(n3)O(n3)O(n^3) алгоритмы для вычисления определителя, но меня интересует какой-то новый подход.) Он...

19
Является ли проблема множества вершин обратной связи разрешимой за полиномиальное время для 3-градусных ограниченных графов?

Набор вершин обратной связи NP-полон для общих графов. Известно, что он является NP-полным для ограниченных графов степени 8 из-за сокращения от покрытия вершины. В статье в Википедии говорится, что она разрешима по времени для ограниченных графов степени 3 и является NP-полной для ограниченных...

19
Вычисление константы Чигера: выполнимо для каких классов?

Как известно, вычисление постоянной Чигера для графика , также известного как изопериметрическая постоянная (поскольку это, по сути, минимальное отношение площади / объема), является NP-полным. Вообще это приблизительно. Мне интересно узнать, известны ли точные полиномиальные алгоритмы для...

19
Аксиомы для кратчайших путей

Предположим, у нас есть неориентированный взвешенный граф G=(V,E,w)G=(V,E,w)G = (V, E, w) (с неотрицательными весами). Предположим, что все кратчайшие пути в GGG единственны. Предположим, у нас есть эти пути (последовательности невзвешенных ребер), но мы не знаем саму G. Можем ли мы создать G ,...

19
Структура данных для кратчайших путей

Пусть GGG - невзвешенный неориентированный граф с nnn вершинами и mmm ребрами. Можно ли предварительно обработать GGG и создать структуру данных размером m⋅polylog(n)m⋅polylog(n)m \cdot \mathrm{polylog}(n) чтобы он мог отвечать на запросы вида «расстояние между uuu и vvv » за время O (n)? Проблема...

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

18
Быстрые алгоритмы ширины дерева

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

18
Восстановление дерева по запросам разделителей

Предположим, что TTT - дерево постоянной степени, структура которого мы не знаем. Проблема состоит в том, чтобы вывести дерево , задавая запросы в форме: «Находится ли узел на пути от узла к узлу ?». Предположим, что на каждый запрос оракул может ответить в постоянное время. Мы знаем значение ,...