Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14737
For citation please use:
Main Title: Maximum dispersion and geometric maximum weight cliques
Author(s): Fekete, Sándor P.
Meijer, Henk
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15964
http://dx.doi.org/10.14279/depositonce-14737
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We consider geometric instances of the problem of finding a maximum weight k-clique of a graph with nonnegative edge weights. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. This problem has been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.
Subject(s): clique
point dispersion
subgraph problem
geometric optimization
approximation
rectilinear norm
Issue Date: 2000
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C27 Combinatorial optimization
90B80 Discrete location and assignment
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2000, 667
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-667-2000.pdf
Format: Adobe PDF | Size: 291.94 kB
DownloadShow Preview
Thumbnail
Report-667-2000.ps
Format: Postscript | Size: 517.06 kB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.