Parameterized dynamic cluster editing

dc.contributor.authorLuo, Junjie
dc.contributor.authorMolter, Hendrik
dc.contributor.authorNichterlein, André
dc.contributor.authorNiedermeier, Rolf
dc.date.accessioned2021-03-15T11:15:22Z
dc.date.available2021-03-15T11:15:22Z
dc.date.issued2020-07-25
dc.description.abstractWe introduce a dynamic version of the NP -hard graph modification problem Cluster Editing . The essential point here is to take into account dynamically evolving input graphs: having a cluster graph (that is, a disjoint union of cliques) constituting a solution for a first input graph, can we cost-efficiently transform it into a “similar” cluster graph that is a solution for a second (“subsequent”) input graph? This model is motivated by several application scenarios, including incremental clustering, the search for compromise clusterings, or also local search in graph-based data clustering. We thoroughly study six problem variants (three modification scenarios edge editing, edge deletion, edge insertion; each combined with two distance measures between cluster graphs). We obtain both fixed-parameter tractability as well as (parameterized) hardness results, thus (except for three open questions) providing a fairly complete picture of the parameterized computational complexity landscape under the two perhaps most natural parameterizations: the distances of the new “similar” cluster graph to (1) the second input graph and to (2) the input cluster graph.en
dc.description.sponsorshipTU Berlin, Open-Access-Mittel – 2020en
dc.description.sponsorshipDFG, 284041127, Algorithmen für Faire Allokationen (AFFA)en
dc.description.sponsorshipDFG, 382063982, Multivariate Algorithmik temporaler Graphprobleme (MATE)en
dc.identifier.eissn1432-0541
dc.identifier.issn0178-4617
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/12837
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-11637
dc.language.isoen
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subject.ddc004 Datenverarbeitung; Informatiken
dc.subject.othercompromise clusteringen
dc.subject.othercorrelation clusteringen
dc.subject.otherfixed-parameter tractabilityen
dc.subject.othergoal-oriented clusteringen
dc.subject.othergraph-based data clusteringen
dc.subject.otherkernelizationen
dc.subject.otherlocal searchen
dc.subject.othermulti-choice knapsacken
dc.subject.otherNP-hard problemsen
dc.subject.otherparameterized complexityen
dc.titleParameterized dynamic cluster editingen
dc.typeArticleen
dc.type.versionpublishedVersionen
dcterms.bibliographicCitation.doi10.1007/s00453-020-00746-yen
dcterms.bibliographicCitation.journaltitleAlgorithmicaen
dcterms.bibliographicCitation.originalpublishernameSpringerNatureen
dcterms.bibliographicCitation.originalpublisherplaceLondon [u.a.]en
dcterms.bibliographicCitation.pageend44en
dcterms.bibliographicCitation.pagestart1en
dcterms.bibliographicCitation.volume83en
tub.accessrights.dnbfreeen
tub.affiliationFak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatik::FG Algorithmik und Komplexitätstheoriede
tub.affiliation.facultyFak. 4 Elektrotechnik und Informatikde
tub.affiliation.groupFG Algorithmik und Komplexitätstheoriede
tub.affiliation.instituteInst. Softwaretechnik und Theoretische Informatikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Luo_etal_Parameterized_2021.pdf
Size:
6.01 MB
Format:
Adobe Portable Document Format

Collections