O. Goldschmidt et al., ON FINDING A BICONNECTED SPANNING PLANAR SUBGRAPH WITH APPLICATIONS TO THE FACILITIES LAYOUT PROBLEM, European journal of operational research, 94(1), 1996, pp. 97-105
Citations number
13
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
The BSPS problem is to find a planar and biconnected spanning subgraph
of a general graph. This problem is related to the planarization prob
lem which seeks a planar spanning subgraph with a maximum number of ed
ges, Like the planarization problem, BSPS has applications in facility
layout problems, which seek the best arrangement of facilities on a s
hop 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.