проблема У меня есть неориентированный граф (с несколькими ребрами), который будет меняться со временем, узлы и ребра могут быть вставлены и удалены. При каждой модификации графика я должен обновлять связанные компоненты этого графика. свойства Дополнительные свойства состоят в том, что никакие два...
Итак, мы все знаем нижнюю границу дерева сравнения на количество худших случаев сравнений, выполненных (детерминистическим) алгоритмом сортировки сравнений. Это не относится к рандомизированной сортировке сравнения (если мы измеряем ожидаемые сравнения для наихудшего случая). Например, для n = 4...
Что меня особенно интересует, так это наличие интересного условия о проценте назначений, которые удовлетворяют формуле 3SAT, чтобы гарантировать, что такие проблемы поддаются решению. Предположим, например, класс задач 3SAT, что из возможных назначений удовлетворяет булевой формуле; мы можем...
Какие проблемы с наилучшим известным коэффициентом аппроксимации достигаются алгоритмом, возвращающим равномерно случайное решение? Я знаю один такой пример для задачи магазина перестановок : в статье « Тесные границы для планирования потока перестановок » Вишванат Нагараджан и Максим Свириденко...
Разложение дерева сложно в худшем случае, но жадный метод кажется почти оптимальным в небольших реальных сетях. Известно ли что-нибудь о сложности разложения дерева «типичного» экземпляра некоторого класса графов? Есть ли пример семейства графов, где жадные методы разложения дерева плохо работают?...
Я ищу имя или какие-либо ссылки на эту проблему. Для заданного взвешенного графа найти разбиение вершин с точностью доустанавливает таким образом, чтобы максимизировать значение срезов: Обратите внимание, что некоторые из множеств могут быть пустыми. Таким образом, проблема, по сути, заключается в...
Линейное программирование, конечно, в настоящее время очень хорошо понято. У нас много работы, которая характеризует структуру возможных решений и структуру оптимальных решений. У нас сильная двойственность, многовременные алгоритмы и т. Д. Но что известно о минимальных максимальных решениях ЛП?...
Дана строка , А палиндром крышка представляет собой последовательность р 1 р 2 ⋯ р м слов р я такое , что р 1 р 2 ⋯ р м = ш , и так , что каждый р я палиндром ,w = σ1σ2… ΣNw=σ1σ2…σnw=\sigma_1\sigma_2\ldots\sigma_nп1п2⋯ рмp1p2⋯pmp_1p_2\cdots p_mпяpip_iп1п2⋯ рм= шp1p2⋯pm=wp_1p_2\cdots p_m = wпяpip_i...
Пусть x1,…,xnx1,…,xnx_1, \ldots, x_n - точки на плоскости R2R2\mathbb{R}^2 . Рассмотрим полный граф с точками в виде вершин и весами ребер . Вы всегда можете найти вес, который составляет не менее \ 2 2 от общего веса? Если нет, то какая константа должна заменить \ frac 2 3 ?2∥xi−xj∥2‖xi−xj‖2\|x_i...
Есть несколько конкурирующих понятий "разреженного графа". Например, встраиваемый в поверхность граф можно считать разреженным. Или график с ограниченной плотностью ребер. Или график с высоким обхватом. График с большим расширением. Граф с ограниченной шириной дерева. (Даже в подполе случайных...
Мы знаем, например, из Koutis-Miller-Peng (на основе работы Spielman & Teng), что мы можем очень быстро решить линейные системы Ax=bAx=bA x = b для матриц AAA которые представляют собой матрицу Лапласа графа для некоторого разреженного графа с неотрицательными весами ребер , Теперь (первый...
Я ищу небольшой граф которого векторное хроматическое число меньше хроматического числа,
Учитывая последовательность из чисел, можно ли ее отсортировать с помощью O ( n ln n ) сравнений и O ( n ) перестановок / ходов? Любой указатель на публикации по этому вопросу или контраргументы, показывающие нижнюю границу Ω ( n ln n ) , поможет.nnnO(nlnn)O(nlnn)O(n \ln...
Я читаю обзоры Тревизана и Ловетта о применении аддитивного комбинаторика в TCS. Большинство этих приложений подпадают под сложность вычислений , например, нижние границы. Интересно, нашла ли аддитивная комбинаторика применение в разработке алгоритмов ? Мотивация для моего вопроса заключается в...
В моей работе возникает следующая проблема: Существует ли известный алгоритм, который аппроксимирует хроматическое число графа без независимого набора порядка 65? (Таким образом, альфа (G) <= 64 известна, а | V | / 64 - тривиальная нижняя, | V | тривиальная верхняя граница. Но существуют ли...
Остаточные автоматы в конечном состоянии (RFSA, определенные в [DLT02]) - это NFA, которые имеют некоторые общие черты с DFA. В частности, для каждого обычного языка всегда существует канонический RFSA минимального размера, а язык, распознаваемый каждым государством в RFSA, является остаточным, как...
Рассмотрим следующую задачу проверки принадлежности к абелевой подгруппе . Входы: Конечная абелева группа с произвольно большим .G = Zd1× Zd1… × ZdмG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}dяdid_i Производящая-набор { ч1, ... , чN}{h1,…,hn}\lbrace...
«Если , существует ли x , y ∈ N , a x 2 + b y = c » является N P -полным.a,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb Nax2+by=cax2+by=cax^2+by=cNPNP\mathsf{NP} К какому классу сложности относится «При условии , существуют ли x , y ∈ N , a x 2 + b y 2 = c »?a,b,c∈Na,b,c∈Na,b,c\in\Bbb...
Очень похоже на мой ранее опубликованный вопрос . На этот раз, однако, график является ненаправленным. Данный Неориентированный граф граммGG без каких - либо множественных ребер или петель, Исходная вершина sss , Целевая вершина Ttt , Максимальная длина пути Lll , Я ищу грамм'G′G' - подграф GGG...
Рассмотрим мерный вектор v, где v i ∈ { 0 , 1 } . Для каждого i мы знаем p i = P ( v i = 1 ) и допустим, что v i независимы. Используя эти вероятности, существует ли эффективный способ итерации по двоичным n- мерным векторам в порядке от наиболее вероятного к наименее вероятному (с произвольным...