Мы определяем язык регулярного дерева, как в книге TATA : это множество деревьев, принятых недетерминированным автоматом конечного дерева (глава 1) или, что эквивалентно, множество деревьев, порожденных грамматикой регулярного дерева (глава 2). Оба формализма очень похожи на хорошо известные...
Известно ли что-нибудь о классе графов с тем свойством, что все максимальные независимые множества имеют одинаковую мощность и, следовательно, являются максимальными IS? Например, возьмем набор точек на плоскости и рассмотрим график пересечений между всеми отрезками между парами точек в наборе....
Том III книги Кнута « Искусство компьютерного программирования» (глава 5, стих 3.2) включает в себя следующую таблицу, в которой перечислено точное минимальное количество сравнений, необходимых для выбора наименьшего элемента TTt из несортированного набора размера NNn для всех 1 ≤ t ≤ n ≤...
Для любого n>0n>0n > 0 я говорю, что последовательность целых чисел в является -полной, если для каждой перестановки из , записанная как последовательность попарно различных целых чисел , последовательность является подпоследовательностью , т. е. существуеттакой, что для всех .{ 1 , … , n } n...
Результат по Robertson и Seymour демонстрирует алгоритм для проверки , является ли фиксированной граф является минор . У меня есть два с половиной вопроса на эту тему:G HO ( n3)О(N3)O(n^3)ггGЧАСЧАСH 1) Похоже, что с тех пор были улучшены этот алгоритм. Какой алгоритм является самым известным в...
Для заданного неориентированного и невзвешенного графа и четного целого числа , какова вычислительная сложность подсчета множеств вершин таких что и подграф графа ограниченный множеством вершин допускает идеальное совпадение? Является ли сложность # P-полной? Есть ли ссылка на эту проблему?k S ⊆ V...
Была ли изучена сложность следующей проблемы? Вход : кубический (или регулярный) граф G = ( V , E ) , естественная верхняя граница t333G=(V,E)G=(V,E)G=(V,E)ttt Вопрос : есть ли раздел на | E | / 3 части размера 3 , так что сумма порядков (необязательно связанных) соответствующих подграфов не...
Лемма о регулярности Семереди говорит, что каждый плотный граф может быть аппроксимирован как объединение многих двудольных графов расширителей. Точнее, существует большинство разбиений вершин на наборов, так что большинство пар множеств образуют двудольные расширители (количество множеств в...
Проблема стабильного брака: http://en.wikipedia.org/wiki/Stable_marriage_problem Мне известно, что для случая SMP возможны многие другие стабильные браки, кроме одного, возвращенного алгоритмом Гейла-Шепли. Однако, если нам дается только , число мужчин / женщин, мы задаем следующий вопрос: можем ли...
Гипотеза реконструкции говорит о том, что графы (по крайней мере, с тремя вершинами) определяются однозначно их вершинами удаленных подграфов. Этой гипотезе пять десятилетий. В поисках соответствующей литературы я обнаружил, что следующие классы графов, как известно, восстанавливаемы: деревья...
Я знаю, что неразрешимо определить, может ли набор плиток укладывать плитку в результате того, что Бергер использовал плитки Ванга . Мой вопрос состоит в том, известно ли также, что неразрешимо определить, может ли один данный фрагмент мозаики составить плоскость - моноэдральный фрагмент . Если это...
Я пытаюсь найти, насколько близки и , когда и является константой, не зависящей от 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...
Для A⊂[n]A⊂[n]A\subset [n] обозначим через aiaia_i в ithithi^{th} наименьший элемент AAA . Для двух kkk -элементных множеств A,B⊂[n]A,B⊂[n]A,B\subset [n] мы говорим, что A≤BA≤ВA\le B если ai≤biai≤bia_i\le b_i для каждого iii . kkk -равномерной Гиперграф H⊂[n]H⊂[n]{\mathcal H}\subset [n] ,...
Если у меня есть набор линейных ограничений, в которых каждое ограничение имеет не более (скажем) 4 переменных (все неотрицательные и с коэффициентами {0,1}, за исключением одной переменной, которая может иметь коэффициент -1), что известно о решении Космос? Меня меньше беспокоит эффективное...
Где я могу найти графики, относящиеся к реальным проблемам? Я знаю два репозитория: Коллекция разреженных матриц Университета Флориды Bodlaender в TreewidthLib
(Я отправил этот вопрос в MathOverflow две недели назад, но пока без точного ответа) У меня есть вопрос о мерах ширины графа неориентированных простых графов. Хорошо известно, что cographs (графы, которые могут быть построены операциями дизъюнктного объединения и дополнения, начиная с изолированных...
Учитывая набор людей, я хотел бы сидеть их для последовательности блюд за столами размера . (Конечно, для каждого приема пищи достаточно столов, чтобы все .) Я бы хотел организовать это так, чтобы никто не делил стол с одним и тем же человеком дважды. Типичными значениями являются и и от 6 до 10...
Я знаю, что тривиально функция OR для переменных может быть точно представлена полиномом следующим образом: , который имеет степень .х 1 , ... , х п р ( х 1 , ... , х п ) р ( х 1 , ... , х п ) = 1 - П п я = 1 ( 1 - х я ) пNnnИкс1, … , ХNx1,…,xnx_1,\ldots, x_nр ( х1, … ,...
Сообщение обновлено 31 августа : ниже оригинального вопроса я добавил резюме текущих ответов. Спасибо за все интересные ответы! Конечно, каждый может продолжать публиковать любые новые результаты. Для каких семейств графов существует алгоритм полиномиального времени для вычисления хроматического...
Время коммутирования в связанном графе определяется как ожидаемое количество шагов в случайном блуждании, начиная с , до посещения узла и затем достижения узла снова. В основном это сумма двух времен удара и .G = ( V, E)гзнак равно(В,Е)G=(V,E)яяiJJjяяiЧАС( я , j )ЧАС(я,J)H(i,j)ЧАС( J , I...