Vis enkel innførsel

dc.contributor.authorBaste, Julien
dc.contributor.authorJaffke, Lars
dc.contributor.authorMasařík, Tomáš
dc.contributor.authorPhilip, Geevarghese
dc.contributor.authorRote, Günter
dc.date.accessioned2020-05-09T16:20:17Z
dc.date.available2020-05-09T16:20:17Z
dc.date.issued2019-11-27
dc.PublishedBaste, Jaffke, Masařík, Philip, Rote. FPT Algorithms for Diverse Collections of Hitting Sets. Algorithms. 2019eng
dc.identifier.issn1999-4893en_US
dc.identifier.urihttps://hdl.handle.net/1956/22160
dc.description.abstractIn 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 k+r 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.en_US
dc.language.isoengeng
dc.publisherMDPIen_US
dc.rightsAttribution CC BYeng
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/eng
dc.subjectsolution diversityeng
dc.subjectfixed-parameter tractabilityeng
dc.subjecthitting setseng
dc.subjectvertex covereng
dc.subjectfeedback vertex seteng
dc.subjectHamming distanceeng
dc.titleFPT Algorithms for Diverse Collections of Hitting Setsen_US
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2020-02-19T10:31:24Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright 2019 The Authorsen_US
dc.identifier.doihttps://doi.org/10.3390/a12120254
dc.identifier.cristin1795759
dc.source.journalAlgorithms


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution CC BY
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution CC BY