An O(n2) time algorithm for the minimal permutation completion problem

In the Minimal Permutation Completion problem, one is given an arbitrary graph G=(V,E) and the aim is to find a permutation super-graph H=(V,F) defined on the same vertex set and such that F⊇E is inclusion-minimal among all possibilities. The graph H is then called a minimal permutation completion o...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2019-02, Vol.254, p.80-95
Main Authors: Crespelle, Christophe, Perez, Anthony, Todinca, Ioan
Format: Article
Language:English
Subjects:
Algorithms
Computer Science
Data Structures and Algorithms
Minimal permutation completion
Permutation graph
Permutations
Polynomial algorithm
Polynomials
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the Minimal Permutation Completion problem, one is given an arbitrary graph G=(V,E) and the aim is to find a permutation super-graph H=(V,F) defined on the same vertex set and such that F⊇E is inclusion-minimal among all possibilities. The graph H is then called a minimal permutation completion of G. We provide an O(n2) incremental algorithm computing such a minimal permutation completion. To the best of our knowledge, this result leads to the first polynomial algorithm for this problem. A preliminary extended abstract of this paper appeared as [4] in the Proceedings of WG 2015.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2018.06.036