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

12
Отрицательные результаты на подходе одинаковых частиц к проблеме изоморфизма графов (GI)

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

12
автоморфизм в гаджетах Кая-Фюрера-Иммермана

В известном контрпримере для изоморфизма графа с помощью метода Вейсфейлера-Лемана (WL) в этой статье Кай, Фюрер и Иммерман построили следующий гаджет . Они строят граф определяемый какXk=(Vk,Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) Vk=Ak∪Bk∪Mk where Ak={ai∣1≤i≤k},Bk={bi∣1≤i≤k}, and Mk={mS∣S⊆{1,2,…,k}, |S| is...

12
Какова сложность этой проблемы пути?

Экземпляр: неориентированный граф с двумя выделенными вершинами s ≠ t и целым числом k ≥ 2 .GGGs≠ts≠ts\neq tk≥2k≥2k\geq 2 Вопрос: существует ли путь в G , такой, что путь касается не более k вершин? (Вершина затрагивается путем, если вершина находится либо на пути, либо имеет соседа на...

12
Подграф, содержащий все узлы и ребра, являющиеся частью простых st-путей с ограниченной длиной в неориентированном графе

Очень похоже на мой ранее опубликованный вопрос . На этот раз, однако, график является ненаправленным. Данный Неориентированный граф граммGG без каких - либо множественных ребер или петель, Исходная вершина sss , Целевая вершина Ttt , Максимальная длина пути Lll , Я ищу грамм'G′G' - подграф GGG...

11
Система «стохастических уравнений»

Рассмотрим граф с вершинами и m ребрами. Вершины помечены действительными переменными x i , где x 1 = 0 фиксировано. Каждое ребро представляет собой «измерение»: для ребра ( u , v ) я получаю измерение z ≈ x u - x v . Точнее, z - действительно случайная величина в ( x u - x v ) ± 1 , равномерно...

11
Для каких семейств графов это обобщенная география в ?

Как упомянул @Marzio, следующая игра называется Generalized Geography . Для графа и начальной вершины игра определяется следующим образом:G = ( V, E)гзнак равно(В,Е)G=(V,E)v ∈ Vv∈Вv \in V На каждом ходу (чередуются два игрока), игрок выбирает , и тогда происходит следующее:u ∈ N( v )U∈N(v)u\in N(v)...

11
Количество достижимых вершин в DAG для каждой вершины

Пусть - ациклический ориентированный граф, такой что out-степень любой вершины равна O ( log | V | ) . Для каждой вершины G мы можем подсчитать количество достижимых вершин, просто запустив dfs из каждой вершины, и это займет O ( | V | | E | ) время. Есть ли лучший способ решить эту...

11
Регулярные графы и изоморфизм

Я хотел бы спросить, есть ли уже опубликованный результат по этому вопросу: Мы берем все возможные разные пути между каждой парой узлов двух соединенных регулярных (со степенью , скажем, числом узлов ) графов и записываем их длины. Конечно, это число различных путей является экспоненциальным. Мой...

11
Полиномиальные задачи в классах графов, заданных запрещенными индуцированными циклическими подграфами

Кросспост из МО . Пусть - класс графов, определенный конечным числом запрещенных индуцированных подграфов, причем все они циклические (содержат хотя бы один цикл).СCC Существуют ли NP-сложные графовые задачи, которые можно решить за полиномиальное время для кроме Clique и Clique cover?СCC Если я...

11
Вычисление расстояний с аппроксимацией менее 2 в общих графиках?

Учитывая взвешенный неориентированный граф с m = o ( n2)m=o(n2)m = o(n^2) ребрами, я хотел бы вычислить расстояния приближения меньше 2 между любой данной парой вершин. Конечно, я хотел бы использовать субквадратичное пространство и время сублинейного запроса. Мне известен результат Цвика, который...

11
Как генерировать графы с известным оптимальным покрытием вершин

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

11
Минимальный эквивалент орграфа относительно источников и стоков

Учитывая ДАГ (ориентированный ациклический граф) , с источником S и раковины T . Найдите DAG D ′ с источниками S и приемниками T с минимальным количеством ребер таким образом, чтобы:DDDSSSTTTD'D′D'SSSTTT Для всех пар существует путь от u до v в D тогда и только тогда, когда существует путь от u до...

11
Наименьшее количество редактирования редактирования между двумя словами

Я ищу структуру данных и алгоритм для вычисления минимального количества изменений, необходимых для преобразования одного слова в другое, учитывая два слова в качестве входных данных, где единственные допустимые изменения добавить букву на одной из конечностей (например, AB -> ABC),...

11
Сложность вычисления среднего расстояния графа

Пусть - среднее расстояние связного графаG .ad(G)ad(G)\rm{ad}(G)G.G.G. Одним из способов вычисления является суммирование элементов матрицы расстояний и соответствующее масштабирование суммы.D ( G ) , Gad(G)ad(G)\rm{ad}(G)D(G),D(G),D(G),GGG Если выходной граф представляет собой дерево, то известно,...

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

Напомним, диаметр графа является длина самой длинной кратчайшему пути в . Для данного графа очевидный алгоритм вычисления решает проблему кратчайшего пути всех пар (APSP) и возвращает длину самого длинного найденного пути.G диам ( G )GGGGGGdiam(G)diam(G)\text{diam}(G) Известно, что задача APSP...

11
Опрос по сепараторам?

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

11
максимизировать MST (G [S]) по всем индуцированным подграфам G [S] в метрическом графе

Была ли эта проблема изучена раньше? Учитывая метрический неориентированный граф G (длины ребер удовлетворяют неравенству треугольника), найдите множество S вершин, таких что MST (G [S]) максимизировано, где MST (G [S]) - минимальное остовное дерево подграфа, индуцированное С. Была ли эта проблема...

11
Выявление бесполезных ребер для кратчайшего пути

Рассмотрим граф (задача имеет смысл как для ориентированных, так и для неориентированных графов). Назовите матрицей расстояний : - это кратчайшее расстояние от вершины до вершины в для некоторой фиксированной функции агрегирования (например, или ).GGGMGMGM_GGGGMG[i,j]MG[i,j]M_G[i,...

11
Какова корреляция между шириной дерева и твердостью экземпляра для случайного 3-SAT?

В этой недавней статье FOCS2013 « Сильные черные ходы к SAT ограниченной длины дерева», составленной Gaspers и Szeider, говорится о связи между шириной дерева графика предложения SAT и твердостью экземпляра. Для случайных 3-SAT, то есть 3-SAT экземпляров, выбранных случайным образом, какова...