Минимальная проблема покрытия пути

10

Мы работаем с распределенными компьютерами, и мы столкнулись с проблемой сложности, которая сводит к минимуму проблему с маршрутом. В настоящее время мы не знаем, как ее решить. Проблема заключается в следующем:

Пусть - некоторое целое число, а - граф, содержащий вершин. Мы помечаем каждую вершину парой такой что . Далее мы называем вершины, используя их метки. Множество ребер в определяется следующим образом: .kZkk(k+1)2(i,j)1ijkZk{((i,j),(i,j))|i>iji}

Каково минимальное покрытие пути ?Zk

Чтение "Nathfos et al." "Проблемы покрытия пути в орграфах и приложениях к тестированию программ". Мы видели, что минимальное покрытие пути равно кардиналу наибольшего несравнимого множества вершин. Мы думали о следующем наборе: с кардиналом .S={(i,j):ik/2j<k/2}k24k2

С уважением,

пьер

пьер
источник
это должно быть вместо в определении ребра ? jjjiZk
Суреш Венкат

Ответы:

10

Похоже, ваш график транзитивно замкнутый DAG, верно? Если это так (а это, вероятно, подтверждение того, что вы говорите в своей цитате из Ntafos и др.), Минимальное количество путей, необходимых для покрытия DAG, - это только максимальное количество попарно несопоставимых элементов; это теорема Дилворта .

Ваш пример может быть достаточно простым, чтобы можно было напрямую идентифицировать этот максимальный несопоставимый набор, но в целом этот набор можно найти за полиномиальное время с помощью алгоритма, основанного на сопоставлении графов. Раздел «Доказательство с помощью теоремы Кёнига» статьи в Википедии о теореме Дилворта объясняет как.

Дэвид Эппштейн
источник