Computing maximum valued regions

Woeginger Gerhard J.: Computing maximum valued regions. In: Acta cybernetica, (10) 4. pp. 303-315. (1992)

[thumbnail of cybernetica_010_numb_004_303-315.pdf]
Cikk, tanulmány, mű

Download (946kB) | Preview


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.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1992
Volume: 10
Number: 4
ISSN: 0324-721X
Page Range: pp. 303-315
Language: English
Place of Publication: Szeged
Related URLs:
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: 315. p. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 10:19

Actions (login required)

View Item View Item