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

DOI10.1016/0377-2217(95)00202-2zbMath0929.90085OpenAlexW1966245710MaRDI QIDQ1278276

Gang Yu, Olivier Goldschmidt, Alexis Takvorian

Publication date: 22 February 1999

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(95)00202-2

zbMATH Keywords

optimizationcomplexitygraph theoryNP-hardfacilitiesplanar and biconnected spanning subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Related Items (2)

A heuristic approach for dividing graphs into bi-connected components with a size constraint ⋮ Maximum weight matching and genetic algorithm for fixed-shape facility layout problem

Cites Work

• Unnamed Item
• Unnamed Item
• Determining the thickness of graphs is NP-hard
• An efficient graph planarization two‐phase heuristic
• On-Line Planarity Testing
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: On finding a biconnected spanning planar subgraph with applications to the facilities layout problem