Fast quasi-threshold editing
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- A Note on "The Comparability Graph of a Tree"
- A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
- Arboricity and Subgraph Listing Algorithms
- Fast quasi-threshold editing
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Graph Partitioning and Graph Clustering
- Multilevel local search algorithms for modularity clustering
- Quasi-threshold graphs
Cited in
(8)- Quasi-threshold graphs
- Linear-time minimal cograph editing
- Fast quasi-threshold editing
- scientific article; zbMATH DE number 910911 (Why is no real title available?)
- Destroying Bicolored $P_3$s by Deleting Few Edges
- An improved kernelization algorithm for trivially perfect editing
- Cluster editing on cographs and related classes
- On the effectiveness of the incremental approach to minimal chordal edge modification
This page was built for publication: Fast quasi-threshold editing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452790)
