찾기 동일한 서브 그래프 감안할 때

:찾기 동일한 서브 그래프 감안할 때

방향성 그래프
노드는
가장자리가

I 라벨이없는 한 번 이상 레이블

같은 레이블이 더 나타날 수있다 노드의 레이블을 고려하여 동등한 가장 큰 (연결된) 하위 그래프 집합을 찾고 싶습니다.

그래프는 거대한 (수백만 개의 노드) 누구에게나 효율적인 솔루션을 알고 있습니까?

알고리즘을 찾고 이상적인 Java 구현을 찾고 있습니다.

업데이트 :이 문제는 NP 완료 가능성이 높습니다. 또한 근사화 된 솔루션을 생성하는 알고리즘에 관심이있을 것입니다.

이 적어도 가까운 것 같다 : Frequent Subgraphs

출처

2009-05-08 kohlerm

어쩌면 그건 나뿐이지만 문제를 이해하지 못했을 것입니다. "평등"이란 무엇입니까? 그것은 각 노드 a에 대해 A : f (a) = b iff label_a == label_b^(out_degree (a), f (x))의 각 x에 대해 다음과 같이 bijective 함수 f : Node_subgraph_A -> Node_subgraph_B가 존재합니다. out_degree (b)에서)? – akappa

예 그게 전부라고 생각합니다. "중복"하위 그래프를 찾고 싶습니다. 결국 그래프는 "동등한"하위 그래프 세트로 파티셔닝됩니다. – kohlerm

내가 강하게 의심은 NP-어렵다.

그래프의 동형 이상의 모든 라벨이 같더라도. (하나의 연결이 끊어진 그래프로 두 그래프를 결합하십시오. 두 개의 원래 그래프와 가장 큰 동등한 서브 그래프입니까?)

동일한 레이블이 비교적 드문 경우 다루기 쉽습니다.

출처

2009-05-08 19:23:55

+1, 좋은 분석. –

좋은 점은 그래프 동형 이성과의 관계를 보지 못했습니다. 그러나 예, 동일한 라벨의 수가 상대적으로 적어야합니다. – kohlerm

찾기 동일한 서브 그래프 감안할 때

답변

관련 문제