Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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 &apos;base&apos; 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 &apos;base&apos; 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