An \(O(n^2)\) time algorithm for the minimal permutation completion problem

DOI10.1016/j.dam.2018.06.036zbMath1404.05205OpenAlexW2888440274MaRDI QIDQ1720313

Anthony Perez, Christophe Crespelle, Ioan Todinca

Publication date: 8 February 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01969498

zbMATH Keywords

polynomial algorithmpermutation graphminimal permutation completion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Permutations, words, matrices (05A05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Linear-time minimal cograph editing

Cites Work

• Unnamed Item
• An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
• Minimal triangulations of graphs: a survey
• Minimal proper interval completions
• Minimal split completions
• Characterizing and computing minimal cograph completions
• On minimal augmentation of a graph to obtain an interval graph
• Minimal comparability completions of arbitrary graphs
• NP-completeness results for edge modification problems
• An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem
• Computing the Minimum Fill-In is NP-Complete
• A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
• Algorithmic Aspects of Vertex Elimination on Graphs
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Algorithms – ESA 2005
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs

This page was built for publication: An \(O(n^2)\) time algorithm for the minimal permutation completion problem