Graph Density Points – An NP-Hard Problem?

I was hoping the project would be smashing through bugs quite quickly at this point but this doesn’t seem to be the case. Anyway, I was looking at the things I wanted to try and achieve in the near future and dividing the quadrants automatically was one of them. in order to increase the amount of ants appearing inside quadrants rather than on the edge of quadrants. I was thinking that the problem might be NP complete.

I was talking to John Howse about the problem of finding a densest point on a graph where the nodes hold binary data, i.e. There is something there, or there isn’t. Like my ant graphs, and he suggested a solution which involved looking at the in-degree for each node and writing a function which gave each node a value depending on how many of the nodes were an in node holding an ant. Using this method the node with the densest area of a small graph can be worked out and it could be expanded out, to a larger graph.

I really doubt I’ll have time to implement this now but I really hope I can.

Leave a Reply

Your email address will not be published. Required fields are marked *