Linear-time minimal cograph editing

DOI10.1007/978-3-030-86593-1_12MaRDI QIDQ2140496zbMATH OpenOpenAlexFDO

Authors 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

• A Linear Recognition Algorithm for Cographs
• An \(O(n^2)\) time algorithm for the minimal permutation completion problem
• An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
• Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
• Characterizing and computing minimal cograph completions
• Cluster editing
• Cograph editing: Merging modules is equivalent to editing P_4s
• Complement reducible graphs
• Complexity and parameterized algorithms for cograph editing
• Complexity of Finding Embeddings in a k-Tree
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Defining and identifying cograph communities in complex networks
• Exact algorithms for cluster editing: Evaluation and experiments
• Fast quasi-threshold editing
• Fully dynamic recognition algorithm and certificate for directed cographs
• Mapping the genome
• Minimal comparability completions of arbitrary graphs
• Minimal proper interval completions
• Minimal split completions
• On minimal augmentation of a graph to obtain an interval graph
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Subexponential parameterized algorithm for interval completion

Cited in

(2)

• Cograph editing: Merging modules is equivalent to editing P_4s
• Cograph generation with linear delay

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2140496)