Рассмотрим следующую проблему - С учетом максимальной плоских графов и G 2 , найти граф с максимальным числом ребер таким образом, что существует подграф (не обязательно индуцируется) в обоих и , изоморфная .G1G1G_1G2G2G_2GGGG1G1G_1G2G2G_2GGG Можно ли это сделать за полиномиальное время? Если да,...
В « Совете начинающему аспиранту » Мануэля Блума : Леонид Левин верит, как я это делаю, какой бы ни был ответ на P = NP? проблема, это не будет так, как вы думаете, должно быть. И он привел несколько замечательных примеров. Например, он дал ФАКТОРИНГОВЫЙ АЛГОРИТМ, который оказался оптимально...
Я ищу реализацию алгоритма для вычисления ширины пути графа. Хорошо известно, что вычисление ширины пути эквивалентно вычислению числа поиска узла, числа разделения вершин или толщины интервала графа. Алгоритм не должен быть очень быстрым; Я хочу запустить его на графиках не более 20 вершин. Мне...
Популярный алгоритм DEFLATE использует кодирование Хаффмана поверх Lempel-Ziv. В общем, если у нас есть случайный источник данных (= 1 бит энтропии / бит), никакое кодирование, включая Хаффмана, скорее всего не сожмет его в среднем. Если бы Лемпель-Зив был «идеальным» (что подходит для большинства...
Ветвление и ограничение - эффективная эвристика для задач поиска, и в Википедии перечислен ряд сложных проблем, где использовались ветвление и привязка. Тем не менее, мне не удалось найти ссылки, позволяющие предположить, что это больше, чем просто «один метод» решения этих проблем. Как ни странно,...
В главе 1 книги «Вероятностный метод» Алона и Спенсера упоминается следующая проблема: Учитывая граф , решите, является ли его граничная связность по крайней мере или нет.GGGn/2n/2n/2 Автор упоминает о существовании алгоритма от Matula и улучшает его до...
Чонг, Хан и Лэм показали, что ненаправленное соединение через st-соединение может быть решено с помощью EREW PRAM за с помощью O ( m + n ) процессоров.O ( log n )О(журналN)O({\log}n)O ( m + n )О(м+N)O(m+n) Каков наиболее известный параллельный алгоритм для st-связности в направленных плоских...
В этой статье Kempe-Kleinberg-Tardos авторы предлагают жадные алгоритмы, основанные на субмодульных функциях, для определения наиболее влиятельных узлов в графе с приложениями к социальным сетям.kkk В основном алгоритм работает следующим образом: S=empty setS=empty setS = {\rm empty~set} выберите...
Мы дали направленный ациклический граф с номером , связанным с каждой вершиной ( г : V → N ), и целевым числом Т ∈ N .G=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N}T∈NT∈NT\in \mathbb{N} Проблема DAG подмножества суммы (может существовать под другим именем, ссылка будет большой) спрашивает , есть...
Я сталкивался с этой проблемой в области физики, довольно далекой от компьютерных наук, но это похоже на вопрос, который был изучен в CS, поэтому я решил попытать счастья, задав его здесь. Представьте, что вам дан набор точек и список некоторых расстояний между точками d i j . Как наиболее...
Хорошо известно , что для каждого матроидов и любой весовой функции , то выходит в алгоритм , которая возвращает максимальный вес основы . Итак, верно ли обратное направление? То есть, если есть какой-то жадный алгоритм, то должна быть и некоторая структура матроида.MMMвесwwGreedyBasis (M, ш...
Один из моих друзей спрашивает меня о следующей проблеме планирования на дереве. Я считаю, что это очень чисто и интересно. Есть ли какая-либо ссылка на это? Проблема: Существует дерево , каждое ребро имеет симметричную стоимость перемещения 1 . Для каждой вершины v i есть задача, которую...
В 1973 году Вайнер дал первое линейное построение суффиксных деревьев. Алгоритм был упрощен в 1976 году МакКрейтом, а в 1995 году - Укконеном. Тем не менее, я нахожу алгоритм Укконена относительно концептуально задействованным. Были ли упрощения алгоритма Укконена с 1995...
У меня есть алгебраическая задача, связанная с векторами в поле GF (2). Пусть v1,v2,…,vmv1,v2,…,vmv_1, v_2, \ldots, v_m - (0,1) -векторы размерности nnn и m=nO(1)m=nO(1)m=n^{O(1)} . Найти алгоритм полиномиального времени, который находит (0,1) -вектор uuu такой же размерности, чтобы uuu не было...
Для ориентированного циклического графа, где вес каждого ребра может быть отрицательным, концепция «кратчайшего пути» имеет смысл, только если нет отрицательных циклов, и в этом случае вы можете применить алгоритм Беллмана-Форда. Тем не менее, я заинтересован в поиске кратчайшего пути между двумя...
Набор-функция fff монотонно субмодулярная , если для всех A,BA,BA,B , f(A)+f(B)≥f(A∪B)+f(A∩B).f(A)+f(B)≥f(A∪B)+f(A∩B). f(A) + f(B) \geq f(A \cup B) + f(A \cap B). Более сильным свойством является...
Я хотел бы знать об истории этих двух терминов: « эффективный », « выполнимый ». Кто использовал их в отношении вычислений / алгоритмов в первый раз? (в современном понимании этих терминов, т.е. 20-го века). Как они стали мейнстримом? Как эти два термина начали использоваться как синонимы? Я знаю,...
Рассмотрим монотонный предикат над множеством степеней (упорядоченный по включению). Под «монотонным» я подразумеваю: такой, что , если то . Я ищу алгоритм, чтобы найти все минимальные элементы , то есть такие, что но , . Поскольку ширина равна n \, выберите n / 22 | п | ∀ x , y ∈ 2 | п | x ⊂ y P (...
Симплексный алгоритм часто трактуется либо в реальной арифметике, либо в дискретном мире с точными вычислениями. Однако, это, кажется, чаще всего реализуется с помощью арифметики с плавающей точкой. Это приводит к вопросу, следует ли рассматривать симплексный алгоритм как числовой алгоритм, в...
Рассмотрим следующую задачу проверки принадлежности к абелевой подгруппе . Входы: Конечная абелева группа с произвольно большим .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...