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...
Elmentve itt :
| Szerző: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
1992
|
| Sorozat: | Acta cybernetica
10 No. 4 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12514 |
| LEADER | 01205nab a2200217 i 4500 | ||
|---|---|---|---|
| 001 | acta12514 | ||
| 005 | 20220613101956.0 | ||
| 008 | 161015s1992 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Woeginger Gerhard J. | |
| 245 | 1 | 0 | |a Computing maximum valued regions |h [elektronikus dokumentum] / |c Woeginger Gerhard J. |
| 260 | |c 1992 | ||
| 300 | |a 303-315 | ||
| 490 | 0 | |a Acta cybernetica |v 10 No. 4 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Kibernetika | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12514/1/cybernetica_010_numb_004_303-315.pdf |z Dokumentum-elérés |