0
나는 에지와 노드 모두 가중치를 갖는 그래프 G = (V, E)를가집니다. 이 그래프를 분할하여 같은 크기의 파티션을 만들고 싶습니다. 파티션 크기의 정의는 sum (vi) -sum (ej)입니다. 여기서 vi는 파티션 내의 노드이고 ej는 해당 파티션의 두 노드 사이의 가장자리입니다. 내 문제는 그래프가 매우 조밀합니다 (거의 완성되었습니다). 그것에 대한 근사 알고리즘이 있습니까?노드 및 에지 가중치를 기반으로 한 그래프 파티셔닝
이것은 빈 크기가 같은 bin packing with overlapping objects의 문제와 다소 유사합니다. 노드의 무게는 크기이고 가장자리의 무게는 두 객체가 얼마나 겹칠 수 있는지 보여줍니다.
모든 가중치를 음수로 설정 한 다음 노드의 가중치를 동일한 노드에 추가하면 동일한 합계 (ei)를 갖는 파티션을 만드는 것이 문제가됩니다 –
서로 다른 파티션에서 두 노드 사이의 가장자리는 어떻게됩니까? 또한 어떤 크기의 파티션이나 분할 영역을 원하십니까? 편집 : 신경 쓰지 마라. 다른 질문을 보면서 어떤 순서의 파티션이나 파티션 사이의 가장자리를 원한다. – jclancy