Balanced landmark-based graph partitioning with application in navigating with limited resources
Chi-Hieu Nguyen, Khanh-Van Nguyen · 2019
We study the problem of graph partitioning balanced on weight vertex where we aim to maximize the average weight of the obtained subgraphs. Our proposed approach is to partition the graph by a graph Voronoi diagram where the Voronoi nodes, considered as landmarks, are carefully selected in some special manner for achieving the mentioned targets. We also introduce a direct application for this problem, namely navigating with limited resources, where one would like to produce an inexpensive navigation device that is although short of battery and of limited memory but still is capable to help showing directions in a long hiking journey in the wilderness. This is achieved by using a specialized map (for navigating) created based on our proposed graph partitioning. We introduce two different heuristic techniques in selecting the landmarks in such a mentioned desired manner. Initial experiments with our proposed algorithms show encouraging results where we can successfully construct a 0.5-balanced partition for all tested graphs.