Вопросы относительно ширины графиков. Графы с малой шириной дерева допускают быстрые алгоритмы «разделяй и властвуй» для многих задач с графами, которые являются NP-сложными на общих графах.
Мой вопрос сегодня (как обычно) немного глупый; но я бы попросил вас рассмотреть это. Я хотел знать о происхождении и / или мотивации концепции ширины дерева. Я уверен, что понимаю, что это используется в алгоритмах FPT, но я не думаю, что это было причиной, почему это понятие было определено. Я...
ST-связность - это проблема определения, существует ли направленный путь между двумя выделенными вершинами и в ориентированном графе . Может ли эта проблема быть решена в пространстве журналов, является давней открытой проблемой. Это называется проблемой противssstttG(V,E)G(V,E)G(V,E)NLNLNLLLL В...
Гипотеза реконструкции говорит о том, что графы (по крайней мере, с тремя вершинами) определяются однозначно их вершинами удаленных подграфов. Этой гипотезе пять десятилетий. В поисках соответствующей литературы я обнаружил, что следующие классы графов, как известно, восстанавливаемы: деревья...
Ширина дерева показывает, насколько близок график к дереву. NP-трудно вычислить ширину дерева. Наиболее известный алгоритм приближения достигает O ( войдите n----√)O(logn)O(\sqrt{{\log}n}) фактор. Теорема Курселя гласит, что любое свойство графов, определяемых в монадической логике второго порядка...
Я пытаюсь найти, насколько близки и , когда и является константой, не зависящей от n (поэтому ). Моя оценка такова: whp, но я не смог доказать это.E [ t w ( G ) ] G ∈ G ( n , p = c / n ) c > 1 E [ t w ( G ) ] = Θ ( n ) t w ( G ) ≤ E [ t w ( G ) ] + o ( n...
При постоянная , можно определить в линейное время, учитывая входной граф G , является ли его древесной шириной есть ≤ K . Однако, когда оба k и G даны в качестве входных данных, проблема NP-трудна. ( Источник ).k ∈ Nk∈Nk \in \mathbb{N}гGG≤ k≤k\leq kКkkгGG Однако, когда входной граф является...
Кто-нибудь знает о программе с открытым исходным кодом для вычисления дерева разложения графов для фиксированной "k" (ширина)? Я знаю, что проблема поиска Tree-Decomposition является NP-Hard для переменной «k», но мои входные экземпляры будут очень маленькими (~ 10 узлов), и «k»...
Множество сложных задач о графах разрешимо за полиномиальное время на графах ограниченной длины деревьев . Действительно, учебники обычно используют, например, набор Independet в качестве примера, что является локальной проблемой . Грубо говоря, локальная проблема - это проблема, решение которой...
Я хотел бы вычислить ширину дерева графика. Есть действительно хорошая эвристика для других задач NP-сложных графов, таких как VF2 для изоморфизма подграфа, например, с кодом, доступным в igraph . Я попробовал их на своих графиках и обнаружил, что они работают очень быстро для моих данных....
Treewidth играет важную роль в алгоритмах FPT, отчасти потому, что многие проблемы FPT параметризуются с помощью treewidth. Связанное, более ограниченное понятие - это пропускная способность. Если граф имеет ширину пути , он также имеет ширину дерева не более k , в то время как в обратном...
Задача Max-Sat просит вас найти назначение формулы CNF, которое удовлетворяет как можно большему количеству предложений. Для более простой задачи SAT существует много известных частных случаев, которые могут быть решены за полиномиальное время, например, мы можем решить 2-SAT за полиномиальное...
Этот вопрос похож на один из моих предыдущих вопросов. Известно, что является запрещенным минором для графов с шириной не более t .Kt+2Kt+2K_{t+2}ttt Существует ли красиво построенное, параметризованное, бесконечное семейство графов (кроме полных графов и сеточных графов), которые являются...
Известен ли следующий класс графов в литературе? Класс графов параметризуется натуральными числами и и содержит каждый граф такой, что для каждой вершины подграф индуцируется на всех вершинах на расстоянии не более от в имеет длину не более .dddTTtG = ( V, E)граммзнак равно(В,Е)G=(V,E)v ∈ Vv∈Вv\in...
Я ищу проблему, которая принадлежит в общих графах, но находится в в графах с ограниченной шириной дерева. На самом деле я думаю, что эти проблемы сложнее, чем использование нормального динамического программирования в ограниченных графах. -ширины графиков для их...
Как известно, древовидная декомпозиция графа состоит из дерева со связанным мешком для каждой вершины , которое удовлетворяет следующим условиям:T T v ⊆ V ( G ) v ∈ V ( T )GGGTTTTv⊆V(G)Tv⊆V(G)T_v \subseteq V(G)v∈V(T)v∈V(T)v \in V(T) Каждая вершина происходит в некотором мешке T .GGGTTT Для каждого...
Когда нам дается древовидная декомпозиция графа с шириной w , есть несколько способов сделать его «красивым». В частности, известно, что его можно преобразовать в разложение дерева, где дерево является двоичным, а его высота равна O ( log n ) . Это может быть достигнуто при сохранении ширины...
Учитывая график, , я хочу , чтобы найти оптимальный г -domination для G . То есть, я хочу подмножество S из V таким образом, что все вершины в G находятся на расстоянии не более чем г от некоторой вершины в S , при сведении к минимуму размера S .G=(V,E)G=(V,E)G = (V, E)rrrGGGSSSVVVGGGrrrSSSSSS Из...
Меня интересуют графики по вершинам, которые можно получить с помощью следующего процесса.nnn Начнем с произвольного графа на вершинах. Пометьте все вершины в как неиспользуемые .GGGGk≤nk≤nk\le nGGG Производят новый граф , добавив новую вершину , который соединен с одним или более неиспользованных...
Можно говорить о ширине дерева булевой схемы, определяя ее как ширину дерева «морализированного» графа на проводах (вершинах), полученного следующим образом: соединяйте провода aaa и ббb всякий раз, когда ббb является выходом затвора, имеющего вход aaa (или наоборот); подключайте провода aaa и ббb...
Пусть G дерево на 2n вершинах. Ширина дерева G, tw (G) = 1. Теперь предположим, что мы добавляем n ребер в G, чтобы получить граф H. Легкая верхняя граница для tw (H) равна n + 1. Является ли это по существу наилучшим возможным? Как-то кажется, что tw (H) должно быть O (sqrt (n)), но это лишь...