Вопросы с тегом «disjoint-paths»

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

Я заинтересован в следующей проблеме. В качестве входных данных нам дается «целевая перестановка» , а также упорядоченный список индексов i 1 , … , i m ∈ [ n - 1 ] . Затем, начиная со списка L = ( 1 , 2 , … , n ) (т. Е. Перестановки тождеств), на каждом временном шаге t ∈ [ m ] мы меняем элемент i...

Простой путь на даге с задними краями

Какова сложность следующей задачи ( P? NP-hard?):∈∈\in Входные данные: направленный ациклический граф , множество обратных ребер и два отдельных узла и .E ′ ⊂ V × V s tD=(V,E)D=(V,E)D=(V,E)E′⊂V×VE′⊂V×VE'\subset V\times Vsssttt Вопрос: Пусть обозначает граф, образованный добавлением к ребер из ....