Linear-time minimal cograph editing

DOI10.1007/978-3-030-86593-1_12OpenAlexW3199287546MaRDI QIDQ2140496

Christophe Crespelle

Publication date: 20 May 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-86593-1_12

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
• Unit interval editing is fixed-parameter tractable
• Exact algorithms for cluster editing: Evaluation and experiments
• Complexity and parameterized algorithms for cograph editing
• Minimal proper interval completions
• Minimal split completions
• Characterizing and computing minimal cograph completions
• Complement reducible graphs
• On minimal augmentation of a graph to obtain an interval graph
• An \(O(n^2)\) time algorithm for the minimal permutation completion problem
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Minimal comparability completions of arbitrary graphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES
• Defining and identifying cograph communities in complex networks
• Fast Quasi-Threshold Editing
• A Linear Recognition Algorithm for Cographs
• Complexity of Finding Embeddings in a k-Tree
• Subexponential parameterized algorithm for Interval Completion
• Cograph editing: Merging modules is equivalent to editing P_4s
• Mapping the genome
• Cluster Editing
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Faster and enhanced inclusion-minimal cograph completion

This page was built for publication: Linear-time minimal cograph editing