Нахождение равных подграфов - PullRequest
Новая
       6

Нахождение равных подграфов

0 голосов
/ 08 мая 2009

Дано:

  • ориентированный граф
  • Узлы имеют метки
  • одна и та же метка может появляться более одного раза
  • края не имеют меток

Я хочу найти множество самых больших (связанных) подграфов, которые равны, принимая во внимание метки узлов.

График может быть огромным (миллионы узлов), кто-нибудь знает эффективное решение для этого?

Я ищу алгоритм и в идеале реализацию Java.

Обновление: поскольку эта проблема, скорее всего, является NP-полной. Я также был бы заинтересован в алгоритме, который производит приближенное решение.

Кажется, это близко, по крайней мере: Частые подграфы

1 Ответ

5 голосов
/ 08 мая 2009

Я сильно подозреваю, что это NP-жесткий.

Даже если все метки одинаковы, это по крайней мере так же сложно, как изоморфизм графов. (Соедините два графика вместе в один несвязный граф; являются ли самые большие равные подграфы двумя исходными графами?)

Если идентичные метки встречаются относительно редко, они могут быть обнаружены.

...