For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Enumerating All Spanning Shortest Path Forests with Distance and Capacity Constraints
Yu NAKAHATA Jun KAWAHARA Takashi HORIYAMA Shoji KASAHARA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2018/09/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
graph algorithm, graph partitioning, decision diagram, frontier-based search, enumeration problem,
Full Text: PDF(1.8MB)
>>Buy this Article
This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.