그래프의 최대 모서리 수

제한된 수의 노드 만 사용하여 그래프에서 최대 모서리 수를 찾는 방법은 N 노드입니다. 선택된 모서리는 그것의 양쪽을 사용합니다.그래프의 최대 모서리 수

2012-05-30 Masood_mj

"선택한 모서리는 양쪽을 사용합니다." 무엇의 양쪽? –

그래프 일치에 대해 이야기하고 있습니까? – ypnos

'n (n-1)/2'이 당신이 요구 한 것입니까? –

알려진 문제. 문제가 k-densest subgraph problem (N이 k 역할을 함)으로 알려져있는 것처럼 들립니다.

나쁜 소식 :이 문제는 NP-hard, even if none of your IPs occur more than three times이거나 입력 그래프가 bipartite 인 것으로 알려져 있습니다. 그래프의 다른 특별한 속성을 알고 있습니까?

더 나쁜 소식 : 최근 문헌을 둘러 보면 빠른 오류 경계가있는 알고리즘조차도 쉽게 사용할 수없는 것처럼 보입니다. 내 생각에,이 문제는 "오직"100 개의 입력 노드로도 고약 할 수 있습니다.

행운을 빈다.

2012-05-30 22:49:32 bennos

답변