An \(O(n^2)\) time algorithm for the minimal permutation completion problem
type: Item
instance of: scholarly article
title: An \(O(n^2)\) time algorithm for the minimal permutation completion problem
zbMATH Open document ID: 1404.05205
author: Christophe Crespelle
author: Anthony Perez
author: Ioan Todinca
published in: Discrete Applied Mathematics
publication date: 2019-02-08T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7018416
zbMATH Keywords: permutation graph
zbMATH Keywords: minimal permutation completion
zbMATH Keywords: polynomial algorithm
MaRDI profile type: Publication
full work available at URL: hal-01969498
OpenAlex ID: W2888440274
cites work: Algorithms – ESA 2005
cites work: NP-completeness results for edge modification problems
cites work: Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
cites work: An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem
cites work: An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
cites work: Minimal triangulations of graphs: a survey
cites work: Minimal split completions
cites work: Minimal comparability completions of arbitrary graphs
cites work: Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
cites work: Characterizing and computing minimal cograph completions
cites work: Q3683903
cites work: A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
cites work: On minimal augmentation of a graph to obtain an interval graph
cites work: Minimal proper interval completions
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Computing the Minimum Fill-In is NP-Complete
DOI: 10.1016/J.DAM.2018.06.036
description: scientific article; zbMATH DE number 7018416