Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Наибольшее по включению паросочетание

Автор: tiktak 9.11.2011, 18:21

Здравствуйте, уважаемые форумчане! Наибольшее паросочетание - паросочетание, не являющееся подмножеством никакого другого паросочетания (т.е. если добавить еще одно ребро в паросочетание, то оно уже перестанет быть таковым). Понятно, что таких паросочетаний может быть несколько. Требуется найти минимальное по мощности из них. Понятно, что эту задачу можно решить перебором. Вопрос: существует ли полиномиальный алгоритм решения этой задачи? Если да, то не могли бы направить в сторону соответствующей литературы/сайта? //Не путать с максимальным паросочетанием (наибольшим по мощности)! //Максимальное паросочетание есть наибольшее по включению, но не обязательно наименьшее по мощности из них.

Автор: maxdiver 10.11.2011, 19:17

Вкратце - нет, не существует. http://en.wikipedia.org/wiki/Edge_dominating_set: Цитата A minimum maximal matching is a minimum edge dominating set Цитата Determining whether there is an edge dominating set of a given size for a given graph is an NP-complete problem (and therefore finding a minimum edge dominating set is an NP-hard problem). Yannakakis & Gavril (1980) show that the problem is NP-complete even in the case of a bipartite graph with maximum degree 3, and also in the case of a planar graph with maximum degree 3.

Автор: tiktak 10.11.2011, 22:35

Спасибо за ответ.

Автор: esperanto 11.11.2011, 13:58

Вместо не существует, верно сказать не известно на сегодняшний день. Возможно что существует

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)