Я хотел бы знать, существуют ли какие-либо бесплатные библиотеки графов для проверки, существует ли определенный набор миноров в данном
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Что если что-либо известно о параметризованной сложности вычисления числа пересечений графа (наименьшее число кликов, необходимых для охвата всех его ребер)? Давно известно, что он является NP-полным, и это, очевидно, FPT, потому что у него есть ядро: если вы можете покрыть граф кликами, то...
Для ориентированного ациклического графа , существует ли структура данных, которая допускает запросы достижимости, не требуя квадратичного пространства или линейного времени? В идеале я ищу алгоритм, использующий только O (log n) пространство на вершину и логарифмическое время,⟨ V,...
Можно ли эффективно задавать ациклический ориентированный граф для следующих операций?G(V,E)G(V,E)G(V,E) isConnected(G,a,b)isConnected(G,a,b)isConnected(G,a,b) : определяет, существует ли путь в от узла до узлаGGGaaabbb link(G,a,b)link(G,a,b)link(G,a,b) : добавляет ребро из в в графеaaabbbGGG...
Будем говорить , что граф является ( , б ) связным , если удаление любых через вершины и любые б ребер из G листьев всегда связного графа. Например, k- связный граф, согласно стандартному определению, ( k - 1 , 0 ) -связный, согласно новому определению. Существует ли алгоритм полиномиальное время ,...
Мне сказали, что есть несколько хороших алгоритмов полиномиального времени для аппроксимации числа простых путей в ориентированном графе от заданной начальной вершины до заданной конечной вершины t . Кто-нибудь знает хорошую ссылку на эту тему?sssTTt Справочная информация: подсчет точного числа...
Сетевой коммутатор (название придумано) выполнен с тремя типами узлов: один начальный узел один конечный узел один или несколько узлов коммутатора Узел коммутатора имеет 3 выхода: влево, вверх, вправо; имеет два состояния L и R и целевое состояние TL или TR . Каждый переключатель может быть пройден...
Мы знаем, что мы можем представить любой плоский граф набором окружностей на плоскости, известным как граф монет . Каждый круг представляет вершину, и между двумя вершинами есть грань, если и только если круги "целуются" на своей границе. Предположим, что вместо этого мы позволяем окружностям...
Как известно, древовидная декомпозиция графа состоит из дерева со связанным мешком для каждой вершины , которое удовлетворяет следующим условиям: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 Для каждого...
Каков наилучший детерминированный результат для поддержания динамического транзитивного замыкания в ориентированном графе только с вставкой ребер? Я читал некоторые статьи по проблеме динамического транзитивного замыкания с вставкой и удалением ребер. Однако, есть ли лучшие алгоритмы для этого...
Я пытаюсь выяснить, как граф путей соответствии с алгоритмом Эппштейна в этой статье работает, и как я могу восстановить k кратчайших путей от s до t с соответствующей конструкцией кучи H ( G ) .P(G)P(G)P(G)kkkssstttH(G)H(G)H(G) Слишком далеко: содержит все ребраоставляя вершину V в графе G ,...
Для заданного ненаправленного графа из вершин, какова наилучшая известная оценка времени выполнения для нахождения подграфа, который является k × k -бикликом? Существуют ли более быстрые параметризованные алгоритмы, чем алгоритм времени для "угадывания" одной стороны биклика и проверки, есть ли...
Я не работаю в теории, но моя работа требует чтения (и понимания) теоретических работ время от времени. Как только я понимаю (набор) результатов, я обсуждаю эти результаты с людьми, с которыми я работаю, большинство из которых также не работают в теории. Во время одного из таких обсуждений возник...
Мы знаем , что краевые раскраски графа являются вершинными раскрасками специального графа, а именно на линию граф от .GGG L(G)L(G)L(G)GGG Существует ли оператор графа такой, что раскраски вершин графа являются краевыми раскрасками графа ? Меня интересует такой оператор графа, который можно...
Край крышки представляет собой подмножество ребер графа, что каждая вершина графа смежна по крайней мере , одного края крышки. В следующих двух статьях говорится, что подсчет краевых покрытий является # P- полным: Простая FPTAS для подсчета краевых покрытий и генерации краевых покрытий для графов...
Я ищу проблемы, которые, как известно, являются NPC для ориентированных графов, но имеют полиномиальный алгоритм для неориентированных графов. Я видел вопрос, касающийся здесь «направленных» проблем, которые проще, чем их «ненаправленный» вариант , но я ищу жесткость на направленной стороне....
Возьмем ориентированный граф края которого украшены натуральным числом. Нам нужно множество всех путей P между двумя вершинами v 1 и v 2 , чтобы каждое последующее ребро в пути было украшено натуральным числом, которое больше натурального числа, украшающего предыдущее ребро.GGGPPPv1v1v_1v2v2v_2...
Любой плоский , соответственно, внешний планарный граф удовлетворяет условию | E ′ | ≤ 3 | V ′ | - 6 , соответственно, | E ′ | ≤ 2 | V ′ | - 3 , для каждого подграфа G ' = ( V ' , E ' ) в G .G=(V,E)G=(V,E)G=(V,E)|E′|≤3|V′|−6|E′|≤3|V′|−6|E'|\le 3|V'|-6|E′|≤2|V′|−3|E′|≤2|V′|−3|E'|\le...
Пусть - множества, которые могут иметь общие элементы. Я ищу наименьшее множество такое, что .S1,S2,…,SnS1,S2,…,SnS_1,S_2,\ldots,S_nXXX∀i,X∩Si≠∅∀i,X∩Si≠∅\forall i,\,X\cap S_i \ne \emptyset У этой проблемы есть имя? Или это сводится к какой-то известной проблеме? В моем контексте описывают...