Класс сложности PPAD (например, вычисление различных равновесий по Нэшу) может быть определен как совокупность полных задач поиска, многократно сводимых к END OF LINE : КОНЕЦ ЛИНИИ : Для заданных схем S и P с n входными битами и n выходными битами, такими что P (0 n ) = 0 n ! = S (0 n ) , найти...
Пусть GGG - невзвешенный неориентированный граф с nnn вершинами и mmm ребрами. Можно ли предварительно обработать GGG и создать структуру данных размером m⋅polylog(n)m⋅polylog(n)m \cdot \mathrm{polylog}(n) чтобы он мог отвечать на запросы вида «расстояние между uuu и vvv » за время O (n)? Проблема...
Я ищу способы поддерживать относительно сбалансированное остовное дерево графа, так как я добавляю новые узлы / ребра графа. У меня есть неориентированный граф, который начинается как один узел, «корень». На каждом шаге я добавляю к графу либо новый узел и ребро, соединяющее его с графом, либо...
Позволять граммграммG быть простым графиком на NNn вершины ( n > 3 )(N>3)(n > 3) без вершины степени n - 1N-1n − 1, Предположим, что для любых двух вершинграммграммG, есть уникальная вершина, смежная с ними обоими. Ван Линт и Уилсон - это курс из курса по комбинаторике , чтобы доказать, что...
Существует ли пример класса графов, для которого задача раскраски вершин находится в P, но независимым множеством является задача
Предположим, у нас есть неориентированный взвешенный граф G=(V,E,w)G=(V,E,w)G = (V, E, w) (с неотрицательными весами). Предположим, что все кратчайшие пути в GGG единственны. Предположим, у нас есть эти пути (последовательности невзвешенных ребер), но мы не знаем саму G. Можем ли мы создать G ,...
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) алгоритмы для вычисления определителя, но меня интересует какой-то новый подход.) Он...
Меня интересуют модели случайных графов, которые похожи на графы реальных компьютерных сетей. Я не уверен, что общая хорошо изученная модель ( n вершин, каждое возможное ребро выбрано с вероятностью p ) подходит для изучения реальных компьютерных сетей (не так ли?).G ( n , p )G(n,p)G(n,p)Nnnпpp...
Ниже MSO обозначает монадическую логику второго порядка графов с определением вершин и ребер. Пусть - младшее замкнутое семейство графов. Из Робертсона и Сеймура теории графов малой , что F характеризуется конечным списком H 1 , H 2 , . , , , Н К , запрещенных несовершеннолетним. Другими словами,...
Набор вершин обратной связи NP-полон для общих графов. Известно, что он является NP-полным для ограниченных графов степени 8 из-за сокращения от покрытия вершины. В статье в Википедии говорится, что она разрешима по времени для ограниченных графов степени 3 и является NP-полной для ограниченных...
Вам дан граф с вершинами. Это может быть двудольный, если хотите. Существует наборов ребер (скажем, дизъюнкт). Меня интересует проблема нахождения как можно меньшего (или даже меньшего) подмножества , такого, чтобы индуцированный граф имел хотя бы одно ребро из каждого класса , для ,G = ( V,...
Множество сложных задач о графах разрешимо за полиномиальное время на графах ограниченной длины деревьев . Действительно, учебники обычно используют, например, набор Independet в качестве примера, что является локальной проблемой . Грубо говоря, локальная проблема - это проблема, решение которой...
Кто-нибудь знает о результате NP-полноты для задачи DOMINATING SET в графах, ограниченной классом плоских двудольных графов максимальной степени 3? Я знаю, что он NP-полон для класса плоских графов максимальной степени 3 (см. Книгу Гарея и Джонсона), а также для двудольных графов максимальной...
Что известно о точной сложности самой короткой проблемы суперструн? Может ли это быть решено быстрее, чем O∗(2n)O∗(2n)O^*(2^n) ? Существуют ли известные алгоритмы, которые решают кратчайшую суперструну без сокращения до TSP? UPD: подавляет полиномиальные факторы.O∗(⋅)O∗(⋅)O^*(\cdot) Самая короткая...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Меня интересует следующая проблема: Имеется ли матрица, существует ли неориентированный граф на вершинах, квадрат матрицы смежности которых является этой матрицей?n×nn×nn\times nnnn Известна ли вычислительная сложность этой проблемы? Примечания: Конечно, это также можно сформулировать как задачу...
Существует ли последовательность неориентированных графов , где каждый имеет ровно вершин, и проблема{ CN}n ∈ N{СN}N∈N\{C_n\}_{n\in \mathbb N}СNСNC_nNNn При заданном и графе является ли индуцированным подграфом в ?NNnграммграммGСNСNC_nграммграммG известно, что он находится в классе ? (Например,...
Как я могу определить количество уникальных простых путей в неориентированном графе? Либо для определенной длины, либо диапазона приемлемых длин. Напомним, что простой путь - это путь без циклов, поэтому я говорю о подсчете количества путей без...
Динамика Глаубера - это марковская цепочка на раскрасках графа, в которой на каждом шаге пытаются перекрасить случайно выбранную вершину в случайный цвет. Он не смешивается для 3-х раскрасок из 5-ти циклов: существует 30 3-раскрасок, но только 15 из них могут быть достигнуты с помощью шагов...
Известен ли следующий класс графов в литературе? Класс графов параметризуется натуральными числами и и содержит каждый граф такой, что для каждой вершины подграф индуцируется на всех вершинах на расстоянии не более от в имеет длину не более .dddTTtG = ( V, E)граммзнак равно(В,Е)G=(V,E)v ∈ Vv∈Вv\in...