How to eat a graph: computing selection sequences for the continuous generalization of road networks
How to eat a graph: computing selection sequences for the continuous generalization of road networks
复制标题
DOI：
10.1145/2666310.2666414
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
Markus Chimani;Thomas C. van Dijk;J. Haunert
中科院分区：
文献类型：
--
作者：
Markus Chimani;Thomas C. van Dijk;J. Haunert
在连通加权图中，考虑按一定顺序一次删除一条边，这样在每次删除后，剩余的边仍然是连通的。我们研究了找到这样一个删除序列的问题，该删除序列使生成的所有不同图中的边的权值总和最大化：在它所在的每个图中计算一条边的权值。这有效地要求高权重边尽可能长时间地保留在图中，并服从连通性。我们将此应用于道路网络泛化，以便生成一系列连续更泛化的道路网络地图，以便这些地图能够很好地结合在一起，而不是单独考虑每个泛化级别。具体来说，我们将研究如何在不同的缩放级别上做出一致的路段选择。我们证明了这个问题是np困难的，并给出了一个最优解的整数线性规划（ILP）。解决这个ILP只适用于小实例。接下来，我们将开发常因子近似算法和启发式算法。我们通过实验证明，这些启发式方法在现实世界的实例中表现良好。
In a connected weighted graph, consider deleting the edges one at a time, in some order, such that after every deletion the remaining edges are still connected. We study the problem of finding such a deletion sequence that maximizes the sum of the weights of the edges in all the distinct graphs generated: the weight of an edge is counted in every graph that it is in. This effectively asks for the high-weight edges to remain in the graph as long as possible, subject to connectivity. We apply this to road network generalization in order to generate a sequence of successively more generalized maps of a road network so that these maps go well together, instead of considering each level of generalization independently. In particular, we look at the problem of making a road segment selection that is consistent across zoom levels. We show that the problem is NP-hard and give an integer linear program (ILP) that solves it optimally. Solving this ILP is only feasible for small instances. Next we develop constant-factor approximation algorithms and heuristics. We experimentally demonstrate that these heuristics perform well on real-world instances.