Проблема нахождения всех максимальных соответствий в общих графиках решена Т. Уно (тем же автором, что и в первой ссылке, приведенной Петром выше) в этой статье 2001 года:
A FastАлгоритм перечисления небипартийных максимальных соответствий
Теперь максимальные (кардинальные) соответствия обычно являются строгим подмножеством максимальных совпадений, но как только известен размер максимального соответствия,максимальные совпадения легко фильтруются, чтобы исключить все, кроме максимальных совпадений.
Однако временная сложность этого «быстрого алгоритма», предложенного Т. Уно, зависит от количества максимальных совпадений.Действительно, для общего графа G (V, E) с | V |вершины и | E |ребра, сложность времени O (| E | + | V | + Δ * N), где Δ - максимальная степень вершин, а N - число максимальных соответствий .
Это не было бы идеально, если отношение максимальных совпадений к максимальным совпадениям является высоким.Однако алгоритм применим к общим графам, поэтому вполне разумно ожидать такого рода поведения при поиске только максимальных соответствий .