Существует несколько интересных классов графов с ограниченной шириной дерева. Например, деревья (treewidth 1), последовательные параллельные графы (treewidth 2), внешнепланарные графы (treewidth 2), -утерплоские графы (treewidth O (k)), графы ширины ветви k (treewidth O (k)), .. ,КkkКkk Вопрос:...
Решение гомоморфизма графа в общем случае является NP-полным. Существуют ли какие-либо результаты, которые изучают эту проблему, когда лежащие в основе графы имеют алгебраическую структуру (например, выбор гомоморфизмов из графов смежных классов Кэли или Кэли в другие графы также с некоторой...
При рассмотрении взаимодействий в сетях обычно очень трудно рассчитать динамический анализ , и используются приближения. Аппроксимации среднего поля обычно заканчиваются полным игнорированием структуры сети, и поэтому редко являются хорошим приближением. Популярным приближением является парное...
В простейших представлениях для графов используются матрицы / списки смежности, что означает, что каждый узел и ребро представлены явно. Важность неявных представлений для графов, демонстрирующих сильные закономерности, давно признана. Например, Galperin & Wigderson (1983), Papadimitriou &...
Пусть . Мне нужно сгенерировать простые графы G обхвата g , чтобы множество всех g- циклов образовывало двойное ребро, покрывающее G (то есть каждое ребро делится ровно двумя g- циклами), и такое, чтобы пересечение любых двух g- циклы - это либо вершина, ребро, либо пустое. Сгенерированные графы...
Пусть наследственный класс графов. (Наследственный = замкнуто относительно взятия индуцированных подграфов.) Пусть обозначит множество -vertex графов в . Допустим, что содержит почти все графы, если доля всех вершинных графов, попадающих в приближается к 1 при...
Я наткнулся на два примера гипотетической сложности некоторых графовых задач. Гипотетическая твердость означает, что опровержение некоторой гипотезы подразумевает NP-полноту соответствующей задачи графа. Например, гипотеза Барнетта утверждает, что каждый 3-связный кубический плоский двудольный граф...
Учитывая граф G1, G2 и G3, мы хотим выполнить тест F изоморфизма между G1 и G2, а также G1 и G3. Если G2 и G3 очень похожи, так что G3 формируется путем удаления одного узла и вставки одного узла из G2, и у нас есть результат F (G1, G2), можем ли мы вычислить F (G1, G3), не вычисляя его с нуля...
Следующий вопрос связан с оптимальностью алгоритма динамического программирования Беллмана-Форда - кратчайшего пути (см. Этот пост для связи). Кроме того, положительный ответ будет означать, что минимальный размер монотонной недетерминированной программы ветвления для задачи STCONN равен . t Θ ( n...
Покрывающее дерево графа называется деревом полноты, если множество его листьев индуцирует полный подграф в графе хоста. Учитывая граф и целое число , какова сложность определения, содержит ли дерево полноты с максимум листами?ггGККkггGККk Причина для того, чтобы задать этот вопрос, состоит в том,...
Учитывая направленный граф, мы хотим решить, содержит ли он направленный цикл четной длины. В этой статье 1997 года, написанной YUSTER и ZWICK, утверждается, что проблема не в том, что она находится в а также в том, что она не является N P -полной.ппPNпNпNP Есть ли какой-либо недавний результат,...
Рассмотрим связный неориентированный граф с неотрицательными весами ребер и двумя выделенными вершинами s,ts,ts,t . Ниже приведены некоторые задачи на пути, которые имеют следующую форму: найдите путь s−ts−ts-t , чтобы некоторая функция весов ребер на пути была минимальной. В этом смысле все они...
Существуют ли классы графов, для которых ширина дерева ограничена сверху функцией числа клика , т.е. ?tw(G)tw(G)tw(G)ω(G)ω(G)\omega(G)tw(G)≤f(ω(G))tw(G)≤f(ω(G))tw(G)\leq f(\omega(G)) Например, это классический факт, что для любого хордального графа мы имеем . Таким образом, классы, связанные с...
Я наткнулся на открытую проблему, поставленную Дэвидом Эппштейном, и меня интересует ее сложность. Он предположил, что он NP-завершен. Ввод: по n матриц 0 и 1, последовательность n 2 0 и 1nnnnnnn2n2n^2 Вопрос: существует ли путь через соседние элементы матрицы, охватывающий каждую запись матрицы...
Кросспост из МО . Изоморфизм цветного графа (ребро) - это GI, который сохраняет цвета (ребер, если он окрашен ребром). Есть несколько сокращений, использующих преобразования / гаджеты (краевого) GI в GI. Для GI с цветным краем самый простой способ - заменить цветной край на гаджет, сохраняющий GI,...
Этот блог рассказывает о создании "извилистых маленьких лабиринтов" с помощью компьютера, перечисляя их. Перечисление может быть выполнено с использованием алгоритма Уилсона для получения UST , но я не помню формулы для того, сколько их там....
Доказательство сложности является основной областью теории вычислительной сложности. Конечная цель этой области состоит в том, чтобы доказать , то есть любой доказатель не может дать доказательство неудовлетворенности данной входной формулой. Nп≠ c o NпNп≠соNпNP\neq coNP Граф - это одна из...
Я решаю проблему «смешивания» наборов перекрывающихся изображений. Эти наборы могут быть представлены неориентированным взвешенным графом, таким как этот: Каждый узел представляет изображение. Перекрывающиеся изображения связаны ребром. Вес края представляет размер области перекрытия ( смешивание...
При введении модульной декомпозиции графа большинство авторов используют граф из 11 вершин, который я копирую из википедии. Вопрос в том, кто является (являются) его первоначальным разработчиком. (Я не спрашиваю, кто нарисовал этот график для Википедии, но его первоначальный источник.) Страница...
Предположим, что у меня есть пPP наборы с элементами, взятыми из рrrвозможные. Каждый набор имеет размерNnn (n <