Graph(?) simplification/optimization problem
![](https://secure.gravatar.com/avatar/b4f6d4f8b501cb05fd054944a166a121.jpg?s=120&d=mm&r=g)
Hi all, Just in case someone knows simple approaches to this type of problem: I am wondering about finding a nicer solution for something like a graph simplification problem. I have pairs of nodes which are developing/moving over time (pairs if there are two, but at each time step they form a circle with an even number, so calling them "n" and "p"): t=0 -n-------p- | | | | / \ | t=1 -n--p-n--p- \ / | | \/ | | t=2 ------n--p- Now the algorithm is supposed to "remove" the new p at t=1 which is there only for a short time and is assumed to be unimportant. Since you can only remove pairs, one of the "n" needs to be removed as well. In this case, deciding which "n" to also delete does not matter much (there are other heuristics to prefer one direction), but in general it can be non-trivial in my case. The overall goal would be to (also) maximize lifespans for individual "nodes", though. The exact optimization function would probably need some tuning, but I am wondering if there is a nice approach for this type of problem. I imagine that I can formulate it as a big integer programming problem, but it doesn't seem that straight forward on first glance. Currently I use some greedy strategies, but while it works fine, I am pretty sure that in some events it gets stuck and does not find the best solution. Anyway, just in case someone happens to know this type of problem and has a tip :). Regards, Sebastian
participants (1)
-
Sebastian Berg