Fast Quasi-Threshold Editing

DOI10.1007/978-3-662-48350-3_22zbMath1465.68209arXiv1504.07379OpenAlexW3099124028MaRDI QIDQ3452790

Michael Hamann, Ben Strasser, Ulrik Brandes, Dorothea Wagner

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.07379

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ Destroying Bicolored $P_3$s by Deleting Few Edges ⋮ Linear-time minimal cograph editing ⋮ Fast Quasi-Threshold Editing ⋮ Faster and enhanced inclusion-minimal cograph completion

Uses Software

• SNAP
• DIMACS
• UbiCrawler
• WebGraph
• NetworKit

Cites Work

• A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
• Fixed-parameter tractability of graph modification problems for hereditary properties
• A polynomial kernel for trivially perfect editing
• Quasi-threshold graphs
• On the threshold of intractability
• Experiments on Density-Constrained Graph Clustering
• Fast Quasi-Threshold Editing
• Arboricity and Subgraph Listing Algorithms
• Graph Partitioning and Graph Clustering
• Multilevel local search algorithms for modularity clustering
• A Note on "The Comparability Graph of a Tree"