I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the sum of the nodes. Any graph that contains edges needs to be reduced by removing one of the two nodes on an edge, until all edges are removed and the graph becomes disjoint. After reducing a graph the total weight should be the maximum possible.
I have already tried an algorithm that simply picks the largest node and discards the connected nodes. This has the problem that it may give a total that is too low.
So I need to find a new algorithm that will be accurate more consistently. My current idea is to look at the graph around each node and determine the difference between that node's weight and the total weight of the connected nodes.
- Select the node with the largest difference
- A positive difference means select the node and ignore the others
- A negative difference means ignore this node and select the others
- For a difference of zero it's not as clear which side to select
- Repeat
At each stage, at least one node (and it's related edges) will be discarded from the graph. Eventually the graph will be made fully disjoint.
Are there any other approaches, and what are the differing costs in terms of time and memory?
Below are some simple examples
Case 1
AA:2, AB:3
No edges, so total weight is 5.
Case 2
BA:3, BB:2, BC:5, BD:2
BB <> BC, BC <> BD
Total weight is 8 (BA + BC)
Case 3
CA:2, CB:3, CC:5, CD:3
CB <> CC, CC <> CD
Total weight is 8 (CA + CB + CD)
My current approach would report 7 (CA + CC)
Case 4
DA:4, DB:3, DC:3, DD:3, DE:4
DA <> DB, DA <> DC, DA <> DD, DC <> DE, DC <> DE
Total weight is 9 (DB + DC + DD)
My current approach would report 8 (DA + DE)
Case 5:
EA:4, EB:3, EC:3, ED:3, EE:4
EA <> EB, EA <> EC, EA <> ED, EB <> EC, EC <> EE, EC <> EE
Note there is complete sub graph between nodes EA, EB, and EC
Total weight is 8 (EA + EE)