An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem
From MaRDI portal
Publication:2827805
DOI10.1007/978-3-662-53174-7_8zbMath1417.05202OpenAlexW2491886730MaRDI QIDQ2827805
Christophe Crespelle, Ioan Todinca, Anthony Perez
Publication date: 21 October 2016
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-53174-7_8
Analysis of algorithms and problem complexity (68Q25) Permutations, words, matrices (05A05) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
On the effectiveness of the incremental approach to minimal chordal edge modification ⋮ An \(O(n^2)\) time algorithm for the minimal permutation completion problem ⋮ Faster and enhanced inclusion-minimal cograph completion
Cites Work
- 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
- 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 $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem
