ProV Logo
0
Fast Quasi-Threshold Editing
Brandes, Ulrik...

Free

Fast Quasi-Threshold Editing by Brandes, Ulrik ( Author )
Lemonjar Open Access
N.A
28-04-2015
We introduce Quasi-Threshold Mover (QTM), an algorithm to solve the quasi-threshold (also called trivially perfect) graph editing problem with edge insertion and deletion. Given a graph it computes a quasi-threshold graph which is close in terms of edit count. This edit problem is NP-hard. We present an extensive experimental study, in which we show that QTM is the first algorithm that is able to scale to large real-world graphs in practice. As a side result we further present a simple linear-time algorithm for the quasi-threshold recognition problem.
-
Article
pdf
36.88 KB
English
-
MYR 0.00
-
https://arxiv.org/abs/1504.07379
Share this eBook