Open access
Date
2022Type
- Book Chapter
ETH Bibliography
yes
Altmetrics
Abstract
We consider the problem of transforming a given graph into a quasi-threshold graph using a minimum number of edge additions and deletions. Building on the previously proposed heuristic Quasi-Threshold Mover (QTM), we present improvements both in terms of running time and quality. We propose a novel, linear-time algorithm that solves the inclusion-minimal variant of this problem, i.e., a set of edge edits such that no subset of them also transforms the given graph into a quasi-threshold graph. In an extensive experimental evaluation, we apply these algorithms to a large set of graphs from different applications and find that they lead QTM to find solutions with fewer edits. Although the inclusion-minimal algorithm needs significantly more edits on its own, it outperforms the initialization heuristic previously proposed for QTM. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000594017Publication status
publishedBook title
Algorithms for Big DataJournal / series
Lecture Notes in Computer ScienceVolume
Pages / Article No.
Publisher
SpringerSubject
Quasi-threshold graph; Trivially perfect graph; Graph editing; Graph clustering; Community detectionOrganisational unit
09610 - Brandes, Ulrik / Brandes, Ulrik
More
Show all metadata
ETH Bibliography
yes
Altmetrics