Analysis of heuristics for finding a maximum weight planar subgraph (Q1062924)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Analysis of heuristics for finding a maximum weight planar subgraph |
scientific article |
Statements
Analysis of heuristics for finding a maximum weight planar subgraph (English)
0 references
1985
0 references
Three heuristics for the problem of finding in an edge-weighted graph a maximum weight planar subgraph are considered in this paper. For each of them, the worst case ratio, i.e., the ratio of the weights of the subgraph chosen in the worst case and the optimal one, is computed. A random model is also studied to show the 'average behaviour' of these approaches.
0 references
polynomial-time heuristics
0 references
facilities location
0 references
edge-weighted graph
0 references
maximum weight planar subgraph
0 references
worst case ratio
0 references
0 references
