Вопросы с тегом «co.combinatorics»

13
Применение номеров Рамси

Определение чисел Рамси следующее: Пусть положительное число такого , что каждый граф порядка по крайней мере содержит либо клику на вершину или множество стабильного на вершинах.R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)aaabbb Я работаю над некоторым расширением номеров Рамси. Хотя исследование...

13
Емкость Уникально Решаемой Головоломки (USP)

В своей основополагающей работе Теоретико-групповые алгоритмы для умножения матриц Кон, Кляйнберг, Сегеди и Уманс вводят концепцию однозначно решаемой головоломки (определено ниже) и емкость USP. Они утверждают, что Копперсмит и Виноград, в своих собственных новаторских работах по умножению матриц...

12
Эффективный алгоритм для почти оптимальной окраски ребер гиперграфов

Проблемы окраски графа уже достаточно сложны для большинства людей . Тем не менее, мне придется столкнуться с трудностями и задать вопрос о раскраске гиперграфа. Вопрос. Какие эффективные алгоритмы существуют для нахождения приблизительно оптимальной раскраски ребер для k-равномерных гиперграфов?...

12
Целочисленное программирование с фиксированным числом переменных

В известной работе 1983 г. Х. Ленстры « Целочисленное программирование с фиксированным числом переменных» говорится, что целочисленные программы с фиксированным числом переменных разрешимы во временном полиноме по длине данных. Я интерпретирую это следующим образом. Целочисленное программирование в...

12
Пограничное разбиение кубических графов на когти и пути

Опять проблема с разделением ребер, сложность которой мне интересна, мотивированная предыдущим моим вопросом . Вход: кубический графG = ( V, E)G=(V,E)G=(V,E) Вопрос: есть ли разбиение на , так что подграф, индуцированный каждым является либо когтем (то есть , часто называемым звездой), либо путём (...

12
Имеют ли графы «внешнего ограниченного рода» постоянную ширину дерева?

Пусть и обозначим через множество всех графов, которые могут быть вложены в поверхность рода , что все вершины расположены на внешней грани . Например, - это множество внешнепланарных графов. Может ли ширина графов в ограничена сверху некоторой функцией от ?G k k G 0 G k...

12
Какова ширина пути 3D-сетки (сетка или решетка) с длиной стороны k?

Я задавал этот вопрос несколько недель назад в mathoverflow , но не получил ответа. Здесь под 3D-сеткой с длиной стороны я имею в виду граф G = ( V , E ) с V = { 1 , … , k } 3 и E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | а - х | + | б - у | + | сkkkG=(V,E)G=(V,E)G=(V,E)V={1,…,k}3V={1,…,k}3V=...

12
Эффективный алгоритм существования перестановки с последовательностью разностей?

Этот вопрос мотивирован этим постом, Можете ли вы определить сумму двух перестановок за полиномиальное время? и мой интерес к вычислительным свойствам перестановок. Разностная последовательность перестановки чисел формируется путем нахождения разности между каждыми двумя соседними числами в...

12
Аддитивные комбинаторные приложения в разработке алгоритмов

Я читаю обзоры Тревизана и Ловетта о применении аддитивного комбинаторика в TCS. Большинство этих приложений подпадают под сложность вычислений , например, нижние границы. Интересно, нашла ли аддитивная комбинаторика применение в разработке алгоритмов ? Мотивация для моего вопроса заключается в...

12
Цитирование несовершеннолетних - это топологические минусы для подкубических графов

Если представляет собой график с максимальной степенью 3 и является минор H , то G является топологическим минор H .граммGGЧАСHHграммGGЧАСHH Википедия цитирует этот результат из «Теории графов» Дистеля. В последней версии книги он указан как Опора 1.7.4. В книге нет доказательств или цитирования....

12
Существует ли книга / обзорная бумага, в которой описываются иерархии языковых классов, свойства замыкания и т. Д.

В настоящее время я занимаюсь исследованиями Формального языка, в которых участвуют классы языков выше обычного, но ниже контекста. Я смотрю на такие вещи, как машины с множеством счетчиков с ограниченным обращением, счетчики с одним стеком, детерминированные КЛЛ и т. Д. Мне интересно, знает ли...

12
Реализация Вильфа-Цейлбергера и связанных с ним методов

В книге A = B Петковсека, Уилфа и Цайльбергера описаны алгоритмы вычисления различных сумм биномов. AFAIK, эти алгоритмы все еще совершенствуются разными авторами. Знаете ли вы, где мы можем найти самые современные реализации этих алгоритмов? А знаете ли вы, существуют ли реализации в некоторых...

12
Комбинаторное вложение графа

Здесь: http://www.planarity.org/Klein_elementary_graph_theory.pdf (в главе «Вложения») дано определение комбинаторного вложения плоского графа. (с определением граней и т. д.) Хотя это можно легко использовать для любого графа, они определяют планарный граф как граф, для которого выполняется...

11
Вычисление макс. H-свободных множеств

В графе независимое множество - это подмножество вершин, которое не содержит ребра в качестве индуцированного подграфа. Проблема нахождения наибольших независимых множеств в графе является фундаментальным и сложным в этом вопросе. Давайте рассмотрим более общий вопрос поиска (размера) наибольшего...

11
Полиномиальные задачи в классах графов, заданных запрещенными индуцированными циклическими подграфами

Кросспост из МО . Пусть - класс графов, определенный конечным числом запрещенных индуцированных подграфов, причем все они циклические (содержат хотя бы один цикл).СCC Существуют ли NP-сложные графовые задачи, которые можно решить за полиномиальное время для кроме Clique и Clique cover?СCC Если я...

11
Регулярные графы и изоморфизм

Я хотел бы спросить, есть ли уже опубликованный результат по этому вопросу: Мы берем все возможные разные пути между каждой парой узлов двух соединенных регулярных (со степенью , скажем, числом узлов ) графов и записываем их длины. Конечно, это число различных путей является экспоненциальным. Мой...

11
Разрешимость заполнения матрицы

Матрица имеет размерность n × n ( n - 1 ) . Мы хотим заполнить A, используя целые числа от 1 до n включительно.AAAn × n ( n - 1 )n×n(n−1)n \times n(n-1)AAA111Nnn Требования: Каждый столбец является перестановкой 1 , … , n .AAA1 , … , n1,…,n1, \dots, n Любая подматрица, образованная двумя строками...

11
Покройте вогнутый многоугольник с минимальным количеством прямоугольников

Я пытаюсь покрыть простой вогнутый многоугольник с минимумом прямоугольников. Мои прямоугольники могут быть любой длины, но они имеют максимальную ширину, и у многоугольника никогда не будет острого угла. Я думал о попытке разложить мой вогнутый многоугольник на треугольники, которые создают набор...

11
Подсчет цветов сетки, которые избегают определенных функций

-раскраске с т × п сеткиkКkm×nм×Nm \times n является функция . Сломан прямоугольник в C является кортежем ( я , я ' , J , J ' ) , удовлетворяющие С ( я , J ) = С ( я ' , J ) = С (C:[m]×[n]→[k]С:[м]×[N]→[К]C:[m] \times [n] \to [k]CCC(i,i′,j,j′)(i,i′,j,j′)(i,i',j,j') - то есть ровно три угла...