Analysis of heuristics for finding a maximum weight planar subgraph (Q1062924)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Analysis of heuristics for finding a maximum weight planar subgraph |
scientific article; zbMATH DE number 3916045
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Analysis of heuristics for finding a maximum weight planar subgraph |
scientific article; zbMATH DE number 3916045 |
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
