редукция однонаправленного графа

[alfur79]

День добрый!

Есть конечный набор данных:
Список исходящих узлов VO = [o1, o2, o3, ...]
Список конечных узлов VI = [i1, i2, i3, i4, ...]
Список граней E = [[o1, i1], [o1, i2], [o1, i3], [o2, i1], [o2, i2], ...]
По ним строится однонаправленный граф: каждая грань начинается в VO и заканчивается в VI.

Задача:
построить кратчайший список "обобщённых граней", например
EO = [[[o1, o2], [i1, i2]], [[o1], [i3]], [[o2], [i2]]]

Что из мат. методов можно эффективно применить: минимальные ДНФ, Backtracking (не хотелось бы), архивацию a'la Huffman, ...?

Благодарю за совет,
Константин

нифига ничего не понятно с вашей странной терминологией... и где это такому учат...

вам дан двудольный граф (множества вершин VO и VI - его доли), и требуется покрыть его множество ребер минимальным числом полных двудольных подграфов (т.е. бикликами)? Эта задача NP-полная, зовется http://en.wikipedia.org/wiki/Bipartite_dimension Так что бэктрэк, да

[alfur79]

нифига ничего не понятно с вашей странной терминологией... и где это такому учат...

Давно уж отучили, повыветрилось

http://en.wikipedia.org/wiki/Bipartite_dimension
Точно, именно эта задача и есть!

С благодарностью,
Константин