Максимальное соответствие веса

В информатике и теории графов — проблема сопоставления максимального веса это проблема поиска во взвешенном графе , сопоставления в котором сумма весов максимальна.

Особым случаем является задача о назначениях , в которой входные данные ограничены двудольным графом , а мощность сопоставления ограничена мощностью меньшего из двух разделов. Другим частным случаем является проблема поиска паросочетания максимальной мощности на невзвешенном графе: это соответствует случаю, когда все веса ребер одинаковы.

Алгоритмы

Существует $O(V^{2}E)$ временной алгоритм для поиска максимального соответствия или максимального веса в графе, который не является двудольным; он принадлежит Джеку Эдмондсу , называется методом путей, деревьев и цветов или просто алгоритмом Эдмондса и использует двунаправленные ребра . Обобщение того же метода можно также использовать для поиска максимальных независимых множеств в графах без клешней .

Существуют более сложные алгоритмы, которые рассматриваются Дуаном и Петти. (см. Таблицу III). В их работе предлагается аппроксимационный алгоритм для задачи сопоставления максимального веса, который работает за линейное время для любой фиксированной границы ошибки.