基于节点和边权重的图划分 [英] Graph partitioning based on nodes and edges weights

问题描述

我有一个图G =（V，E），它的边和节点都有权重。我想分割这个图来创建相同大小的分区。分区大小的定义是sum（vi）-sum（ej）其中vi是该分区内的节点，ej是该分区中两个节点之间的边缘。在我的问题中，图很密集（几乎完成）。有什么近似算法吗？

这在某种程度上类似于具有重叠对象的垃圾箱，垃圾箱具有相同的尺寸。节点的重量是它们的大小和边的重量显示两个对象可以重叠多少。

我认为如果你使用METIS程序解决问题。
您可以下载此链接的这个程序
http：// glaros .dtc.umn.edu / gkhome / views / metis
它有一个很好的文档和非常快的程序。

I have a graph G=(V,E) that both edges and nodes have weights. I want to partition this graph to create equal sized partitions. The definition of the size of partition is sum(vi)-sum(ej) where vi is a node inside that partition and ej is an edge between two nodes in that partition. In my problem the graph is very dense (almost complete). Is there any approximation algorithm for that?

This is somehow similar to the problem in bin packing with overlapping objects where bins have the same size. Weight of nodes are their size and weight of Edges show how much two object can overlap.

解决方案

I think if you use METIS program solved problem. you can download this program of this link http://glaros.dtc.umn.edu/gkhome/views/metis it has a good documentation and very fast program.

这篇关于基于节点和边权重的图划分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！