FPT Algorithms for Diverse Collections of Hitting Sets
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404212" target="_blank" >RIV/00216208:11320/19:10404212 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=k-Bqq.u7Ca" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=k-Bqq.u7Ca</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.3390/a12120254" target="_blank" >10.3390/a12120254</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
FPT Algorithms for Diverse Collections of Hitting Sets
Popis výsledku v původním jazyce
In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of 'base' solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest.
Název v anglickém jazyce
FPT Algorithms for Diverse Collections of Hitting Sets
Popis výsledku anglicky
In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of 'base' solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
—
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2019
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Algorithms
ISSN
1999-4893
e-ISSN
—
Svazek periodika
12
Číslo periodika v rámci svazku
12
Stát vydavatele periodika
CH - Švýcarská konfederace
Počet stran výsledku
18
Strana od-do
1-18
Kód UT WoS článku
000505741500024
EID výsledku v databázi Scopus
2-s2.0-85079697264