I have 2D, 3D and 4D grid graphs. I want to partition them in such a way that number of vertices in each partition would be almost equal and edge cuts are minimized. These grid have equal size over each dimension. eg. fig shows 2D grid of dimension 10*10 & 3D grid of 5*5*5 dimension.
I am interested in any literature for techniques defined to partition such graphs.
Does anyone know if any software tool which considers the topological properties of grid graphs to partition them effectively?
Dear Ravikant,
My colleague Pavle V, M, Blagojević from the Mathematical Institute of the Serbian Academy of Sciences and Arts is working in topology and in particular on 'Ham sandwich theorem' which considers partition of sets of points into classes according to different criteria. I am not sure whether this will solve your problem, but you can contact him here on ResearchGate and at least get a good advice.
A. Krapež
I dont have any references in mind but I remember there is a spectral approach.
Re answer by P. Sole:
If it regards the Spectral graph theory I can again give the names of two researchers from my Institute working in this field: Dragoš Cvetković and Slobodan Simić. The second one is on RG but I am not sure about D. Cvetković.
A. Krapež
OK the reference I had in mind was
http://www.sciencedirect.com/science/article/pii/0012365X9390151I
Delorme is in graph theory paradise but maybe Polyak is still active...
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs