Вопросы с тегом «matching»

Сопоставление - это подмножество ребер графа, такое, что ни одно ребро в этом подмножестве не имеет общей вершины с другим.

26
Рабин – Карп - Карп – Рабин

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

24
Вычисление расстояния Левенштейна быстро

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

24
Каково максимальное количество стабильных браков для случая проблемы стабильного брака?

Проблема стабильного брака: http://en.wikipedia.org/wiki/Stable_marriage_problem Мне известно, что для случая SMP возможны многие другие стабильные браки, кроме одного, возвращенного алгоритмом Гейла-Шепли. Однако, если нам дается только , число мужчин / женщин, мы задаем следующий вопрос: можем ли...

20
n-мерное сопоставление с образцом

Каковы некоторые известные результаты для нахождения точного n-мерного подмассива внутри n-мерного массива? В 1D это просто проблема соответствия строк, KMP делает это за линейное время. В 2D эта статья показала, что это можно сделать за линейное время с небольшим дополнительным пространством....

18
Максимальное количество внутренне непересекающихся вершин нечетной длины st путей

Пусть - неориентированный простой граф, и пусть - различные вершины. Пусть длина простого st-пути будет числом ребер на пути. Мне интересно вычислить максимальный размер набора простых st-путей, чтобы каждый путь имел нечетную длину, а наборы вершин каждой пары путей попарно пересекались только по...

16
Можем ли мы решить, есть ли у перманента уникальный термин?

Предположим, нам дана матрица n по n, M, с целочисленными элементами. Можем ли мы решить в P, существует ли перестановка такая, что для всех перестановок мы имеем ?σσ\sigmaπ≠ σπ≠σ\pi\ne\sigmaΠ Мя σ( я )≠ П Мя π( я )ΠMяσ(я)≠ΠMяπ(я)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Замечания. Конечно, можно...

15
Сложность топологической сортировки с ограниченными позициями

Мне дают в качестве входных данных DAG из n вершин, где каждая вершина x дополнительно помечена некоторым S ( x ) ⊆ { 1 , … , nGGGnnnxxx .S(x)⊆{1,…,n}S(x)⊆{1,…,n}S(x) \subseteq \{1, \ldots, n\} Топологическим видом является биекция f из вершин G в { 1 , … , n } такая, что для всех x , y , если в G...

14
Идеальные совпадения на шахматной доске?

Рассмотрим проблему определения максимального количества рыцарей, которых можно разместить на шахматной доске, чтобы двое из них не атаковали друг друга. Ответ 32: найти идеальное соответствие не так уж и сложно (график, индуцированный ходами коня, является двудольным, и есть идеальное соответствие...

14
Достаточно ли, чтобы линейные программные ограничения были выполнены в ожидании?

В статье « Рандомизированный анализ ранга-двойственности RANKING для сопоставления двухчастных он- лайн , доказывая, что алгоритм RANKING является -конкурентоспособным, авторы показывают, что двойственное возможно в ожидание (см. лемму 3 на стр. 5). Мой вопрос:( 1 - 1е)(1-1е)\left(1 -...

14
Сколько отрицаний нам нужно для вычисления монотонных функций?

Разборов доказал, что соответствие монотонной функции отсутствует в мП . Но можем ли мы вычислить соответствие, используя схему полиномиального размера с несколькими отрицаниями? Существует ли P / поли схема с O(nϵ)O(nϵ)O(n^\epsilon) отрицаниями, которая вычисляет совпадение? Каков компромисс между...

13
Редактировать расстояние с помощью операций перемещения

Мотивация: соавтор редактирует рукопись, и я хотел бы увидеть четкое резюме изменений. Все инструменты, подобные "diff", как правило, бесполезны, если вы одновременно перемещаете текст (например, реорганизуете структуру) и делаете локальные правки. Неужели так сложно понять это правильно?...

12
Улучшена нижняя граница сложности монотонной схемы идеального соответствия?

Разборов доказал, что каждая монотонная схема, которая вычисляет функцию идеального соответствия для двудольных графов, должна иметь как минимум вентилей (он назвал это «логическим перманентом»). Была ли лучшая оценка снизу для той же проблемы доказана с тех пор? (скажем 2 n ϵ ?) Насколько я помню,...

12
Покрывающая струна палиндромами

Дана строка , А палиндром крышка представляет собой последовательность р 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...

11
Максимальное совпадение M с условием G [M] не содержит 2K_2

Есть ли в литературе что-нибудь близкое к следующей проблеме: Дан двудольный граф G ( V, E)G(V,E)G(V,E) со сбалансированным разделением на две части { U, Вт}{U,W} \{U,W\} существует ли идеальное соответствие MM M в гG G такой, что на каждые 2 ребра U1вес1,U2вес2∈ Mu1w1,u2w2∈Mu_1w_1, u_2w_2\in M...

11
Расширение проблемы стабильного брака?

Это может звучать больше как вопрос социальных наук, чем вопрос TCS, но это не так. Читая « Рандомизированные алгоритмы », описывающие проблему стабильного брака, можно прочитать следующее (p54) «Можно показать, что для каждого списка предпочтений существует, по крайней мере, один стабильный брак....

11
Слова Фибоначчи

В моем старом учебнике по чешскому алгоритму я столкнулся со следующей проблемой, к сожалению, без подсказок и решений. «Мы определяем слова Фибоначчи как , , , где и - общие буквы. Как в данном строка (над потенциально большим алфавитом) вы можете найти самое длинное подслово Фибоначчи за линейное...

10
Максимальный вес соответствия и субмодульные функции

Для двудольного графа с положительными весами пусть с равным максимальному совпадению весов в графе .f : 2 U → R f ( S ) G [ S ∪ V ]G=(U∪V,E)G=(U∪V,E)G = (U \cup V, E)f:2U→Rf:2U→Rf: 2^U \rightarrow \mathbb{R}f(S)f(S)f(S)G[S∪V]G[S∪V]G[S\cup V] Правда ли, что субмодулярная...

10
Сложность гомогенизации строки

Мотивация : Разрабатывая инструменты для управления версиями данных, мы в конечном итоге изучили алгоритмы «различий» двух наборов целых чисел, предложив последовательность преобразований, которые переводят один набор целых чисел в другой. Мы смогли свести эту проблему к следующей очень...

10
Монотонные биекции между списками интервалов

У меня есть следующая проблема: Вход: два набора интервалов и T (все конечные точки являются целыми числами). Вопрос: существует ли монотонная биекция f : S → T ?SSSTTTе: S→ Tf:S→Tf:S \to T Биекция монотонна WRT порядка включения множества на и T . ∀ X ⊆ Y ∈ S , f ( X ) ⊆ f ( Y )SSSTTT∀ X⊆ Y∈ S,...

10
Могут ли суффиксные деревья использоваться для поиска всех общих подстрок?

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