On finding a biconnected spanning planar subgraph with applications to the facilities layout problem

On finding a biconnected spanning planar subgraph with applications to the facilities layout problem

0.00 Avg rating0 Votes
Article ID: iaor1999540
Country: Netherlands
Volume: 94
Issue: 1
Start Page Number: 97
End Page Number: 105
Publication Date: Oct 1996
Journal: European Journal of Operational Research
Authors: , ,
Keywords: graphs
Abstract:

The BSPS problem is to find a planar and biconnected spanning subgraph of a general graph. This problem is related to the planarization problem which seeks a planar spanning subgraph with a maximum number of edges. Like the planarization problem, BSPS has applications in facility layout problems, which seek the best arrangement of facilities on a shop floor, such that the adjacency of facilities which share material flows is maximized. In this paper we prove that the BSPS problem is NP-hard. We develop a heuristic algorithm and present empirical results that show this heuristic to be successful in most cases.

Reviews

Required fields are marked *. Your email address will not be published.