Вопросы с тегом «ds.algorithms»

Учитывая конечную плоскость, у меня есть шестиугольная мозаика этой плоскости с регулярным шестиугольником фиксированного размера. Затем я вычисляю граф Делоне G для тесселяции. Учитывая такой граф G, я удаляю определенные множества узлов в этом графе, чтобы получить несколько подграфов G. Мне...

Я просматривал оригинальную статью Les Valiant, и мне было тяжело с предложением 4.3 на странице 10 статьи. Я не могу понять, почему это так, что если существует генератор с определенными значениями для с базисом { ( a 1 , b 1 ) … ( a r , b r ) } , то существует некоторый генератор с таким же v a l...

Меня интересуют явные примеры графиков, для которых применение алгоритма Геманса и Уильямсона для аппроксимации максимальных сечений приводит к коэффициенту аппроксимации 0,878…. Алгоритм создания таких экземпляров был бы идеальным, явные примеры и ссылки были бы...

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

Была проделана большая работа по вычислительным задачам для частичных порядков (например, распознавание, число переходов, распознавание графа сравнимости и т. Д.). Мне любопытно, какая работа, связанная с решетками, была проделана. Я искал вокруг и не нашел много похожих работ для решеток. В...

ПРИМЕЧАНИЕ : вопрос был переформулирован в моих ответах: Предполагая теперь, что мы можем найти самых низких предков родного брата за время , может ли ANN действительно выполняться за ?O(1)O(1)O(1)O(logn)O(log⁡n)O(\log n) Квадро - эффективные пространственные показатели. У меня есть головоломка с...

Скажем, у нас есть многогранник в стандартной форме: A x = bх ≥0Ax=bx≥0\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*} Существуют ли какие-либо известные способы нахождения гиперплоскости которая разбивает многогранник таким...

Существует ли алгоритм полиномиального времени, чтобы найти - если он существует - остовный паук данного графа ? Паук - это дерево с не более чем одним узлом со степенью больше 2: я знаю, что различные условия степеней на (по существу, достаточно большие степени узлов) гарантируют существование...

У меня есть 400 шаров, из которых 100 - красные, 40 - желтые, 50 - зеленые, 60 - синие, 70 - фиолетовые, 80 - черные. (шарики одного цвета идентичны) мне нужен эффективный алгоритм перетасовки, чтобы после перетасовки шары были в списке, и Любые 3 последовательных шара не одного цвета. Например, я...

Я хотел бы знать, изучалась ли ранее простая проблема и известно ли какое-либо решение. Пусть G - конечная (MxN) сетка, S - подмножество клеток G («крошки»). Говорят, что две крошки (локально) связаны, если их координаты отличаются не более чем на один (т. Е. Если они нарисованы в виде квадратов,...

Для заданного невзвешенного плоского графа и набора пар вершин ( - константа) найдите непересекающихся вершин (кроме исходных) путей от до таких что длина самого длинного пути сведена к минимуму.( с , т1) , ... , ( s , тК)(s,T1),...,(s,TК)(s,t_1),\dots,(s,t_k)k ≥ 2К≥2k\ge2ККksssTяTяt_i Вопрос: есть...

Предположим, что мы рассматриваем 3-SAT с переменными и c предложениями. Я исследую метод, который, по-видимому, использует O ( v 2 + log c ) время / пространство для решения любой задачи SAT, соответствующей данному описанию, с точностью до ошибки, которую можно скорректировать до произвольной...

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

В статье « О двух проблемах теории информации» Эрдёс и Реньи дают нижние оценки минимального количества взвешиваний, которое необходимо сделать, чтобы определить количество фальшивых монет в наборе из монет.NNn Более формально: Поддельные монеты имеют меньший вес, чем правильные монеты; веса и как...

Пусть - неориентированный граф. Разложение V на непересекающиеся подмножества V я называюсь разложением Гамильтон из G , если подграф , индуцированный каждое множество V я либо граф Гамильтон , либо состоит из одного ребра с | V я | = 2 .G=(V,E)G=(V,E)G=(V,E)VVVViViV_iGGGViViV_i|Vi|=2|Vi|=2|V_i|=2...

Я пытаюсь использовать деревья суффиксов для сравнения последовательностей строк. Я нашел реализации / теорию для самой длинной общей проблемы подстроки, используя деревья суффиксов. Однако, то, что я ищу, является обсуждением связанной проблемы - "все общие подстроки". В частности, у меня есть...

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

В простейших представлениях для графов используются матрицы / списки смежности, что означает, что каждый узел и ребро представлены явно. Важность неявных представлений для графов, демонстрирующих сильные закономерности, давно признана. Например, Galperin & Wigderson (1983), Papadimitriou &...

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

Кажется, есть много рандомизированных алгоритмов для проверки полиномиальной идентичности, проверяя, равен ли данный полином нулю. Есть ли какие-либо результаты алгоритмов, которые делают своего рода оценку полиномов по определенному набору точек? Это может быть, например, аппроксимация, для какой...