Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Maximum dispersion and geometric maximum weight cliques
Author(s): Fekete, Sándor P.
Meijer, Henk
Type: Research Paper
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
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:
Format: Adobe PDF | Size: 291.94 kB
DownloadShow Preview
Format: Postscript | Size: 517.06 kB

Item Export Bar

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