Computing maximum valued regions
We consider the problem of finding optimum connected configurations in the plane and in undirected graphs. First, we show that a special case concerning rectilinear grids in the plane and arising in oil business is NPcomplete, and we present a fast approximation algorithm for it. Secondly, we identi...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Published: |
1992
|
| Series: | Acta cybernetica
10 No. 4 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Subjects: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12514 |
| Summary: | We consider the problem of finding optimum connected configurations in the plane and in undirected graphs. First, we show that a special case concerning rectilinear grids in the plane and arising in oil business is NPcomplete, and we present a fast approximation algorithm for it. Secondly, we identify a number of polynomial time solvable special cases for the corresponding problem in graphs. The special cases include trees, interval graphs, cographs and split graphs. |
|---|---|
| Physical Description: | 303-315 |
| ISSN: | 0324-721X |