Cluster Editing for Multi-Layer and Temporal Graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00377842" target="_blank" >RIV/68407700:21240/24:00377842 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/s00224-024-10174-y" target="_blank" >https://doi.org/10.1007/s00224-024-10174-y</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00224-024-10174-y" target="_blank" >10.1007/s00224-024-10174-y</a>
Alternative languages
Result language
angličtina
Original language name
Cluster Editing for Multi-Layer and Temporal Graphs
Original language description
Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive a set of graphs on the same vertex set, called layers and aim to transform all layers into cluster graphs (disjoint unions of cliques) that differ only slightly. More specifically, we want to mark at most d vertices and to transform each layer into a cluster graph using at most k edge additions or deletions per layer so that, if we remove the marked vertices, we obtain the same cluster graph in all layers. In Temporal Cluster Editing we receive a sequence of layers and we want to transform each layer into a cluster graph so that consecutive layers differ only slightly. That is, we want to transform each layer into a cluster graph with at most k edge additions or deletions and to mark a distinct set of d vertices in each layer so that each two consecutive layers are the same after removing the vertices marked in the first of the two layers. We study the combinatorial structure of the two problems via their parameterized complexity with respect to the parameters d and k, among others. Despite the similar definition, the two problems behave quite differently: In particular, Multi-Layer Cluster Editing is fixed-parameter tractable with running time k^{O(k+d)}s^{O(1)} for inputs of size s, whereas Temporal Cluster Editing is W[1]-hard with respect to k even if d=3.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theory of Computing Systems
ISSN
1432-4350
e-ISSN
1433-0490
Volume of the periodical
68
Issue of the periodical within the volume
5
Country of publishing house
US - UNITED STATES
Number of pages
52
Pages from-to
1239-1290
UT code for WoS article
001261989700001
EID of the result in the Scopus database
2-s2.0-85197891440