On the k-colored Rainbow Sets in Fixed Dimensions

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00550972" target="_blank" >RIV/67985807:_____/21:00550972 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-030-92681-6_46" target="_blank" >http://dx.doi.org/10.1007/978-3-030-92681-6_46</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-92681-6_46" target="_blank" >10.1007/978-3-030-92681-6_46</a>

Result language

angličtina

Original language name

On the k-colored Rainbow Sets in Fixed Dimensions

Original language description

In this paper, we introduce a variant of the minimum diameter color spanning set (MDCSS) problem. Let P be a set of n points of m colors in Rd . For a given k, our objective is to find a set with k points of different colors that admits the minimum possible diameter. Such a set is called a k-rainbow set. This problem has applications in database queries, mostly composed by weighted points (i.e., a positive value is assigned to each point as its weight), and seeking a maximum weight k-rainbow set. We first assume the points have equal weight and design an FPT algorithm, which we generalize to the weighted version. We also solve the decision and the enumeration version of the problem by introducing a reduction to all maximal independent sets of a bipartite graph. We also introduce a 1.154-approximation algorithm for this problem and a 2.236-approximation for the enumeration version, and we perform some experimental studies on a real data-set, as well as providing several analyses of the data-set based on the outputs of our algorithm. Our exact algorithms and the approximation algorithm for the enumeration problem have a complexity being near-linear to n in R2 .

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Structural properties of visibility in terrains and farthest color Voronoi diagrams</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2021

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Combinatorial Optimization and Applications: 15th International Conference, COCOA 2021, Tianjin, China, December 17–19, 2021, Proceedings

ISBN

978-3-030-92680-9

ISSN

0302-9743

e-ISSN

—

Number of pages

15

Pages from-to

587-601

Publisher name

Springer

Place of publication

Cham

Event location

Tianjin

Event date

Dec 17, 2021

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—