|
|||||
|
|
Analysis of heuristics for finding a maximum weight planar subgraph |
|
| Authors: | ME Dyer LR Foulds AM Frieze |
| Institution: | Department of Mathematics and Statistics, Teesside Polytechnic, Middlesbrough, Cleveland TS1 3BA, United Kingdom;Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, U.S.A.;Department of Computer Science and Statistics Queen Mary College, University of London, London, E1 4NS, United Kingdom |
| Abstract: | The problem of identifying a planar subgraph of maximum total weight in an edge-weighted graph has application to the layout of facilities in a production system and elsewhere in industrial engineering.This problem is NP-hard, and so we confine our attention to polynomial-time heuristics. In this paper we analyse the performance of some heuristics for this problem. |
| Keywords: | Graphs heuristics computational analysis probability facilities location |
| 本文献已被 ScienceDirect 等数据库收录！ | |