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

Christophe Crespelle; Anthony Perez; Ioan Todinca

doi:10.1016/j.dam.2018.06.036

Home
Submit
Browse all HAL
Inria publications
Search
Services
Help
OpenAccess
- Inria supporting open science

Journal articles

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

Christophe Crespelle ¹ Anthony Perez ² Ioan Todinca ²

1 DANTE - Dynamic Networks : Temporal and Structural Capture Approach

Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes

2 LIFO - Laboratoire d'Informatique Fondamentale d'Orléans

Christophe Crespelle ¹ AuthorId : 1442238
Author

Anthony Perez ² AuthorId : 833977
Author IdHAL : anthony-perez

Ioan Todinca ² AuthorId : 112453
Author

1 DANTE - Dynamic Networks : Temporal and Structural Capture Approach (46 Allée d'Italie 69364 Lyon France - France) StructId : 1079003

Inria Grenoble - Rhône-Alpes (Inovallée 655 avenue de l'Europe 38330 Montbonnot - France) StructId : 2497
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France) StructId : 300009
LIP - Laboratoire de l'Informatique du Parallélisme (46 Allée d'Italie 69364 LYON CEDEX 07 - France) StructId : 35418
- CNRS - Centre National de la Recherche Scientifique : UMR5668 / URA1398 (France) StructId : 441569
- Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France) StructId : 300009
- UCBL - Université Claude Bernard Lyon 1 (43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex - France) StructId : 194495
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- ENS Lyon - École normale supérieure - Lyon (15 parvis René Descartes - BP 7000 - 69342 Lyon Cedex 07 - France) StructId : 6818
IXXI - Institut Rhône-Alpin des systèmes complexes (46, allée d'Italie 69007 LYON - France) StructId : 1079001
- ENS Lyon - École normale supérieure - Lyon (15 parvis René Descartes - BP 7000 - 69342 Lyon Cedex 07 - France) StructId : 6818
- UL2 - Université Lumière - Lyon 2 (86, rue Pasteur - 69007 Lyon - France) StructId : 33804
- UJML - Université Jean Moulin - Lyon 3 (6 cours Albert Thomas - 69008 Lyon - France) StructId : 118744
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- UCBL - Université Claude Bernard Lyon 1 (43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex - France) StructId : 194495
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- INSA Lyon - Institut National des Sciences Appliquées de Lyon (20 Avenue Albert Einstein, 69621 Villeurbanne cedex - France) StructId : 219748
  - Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
  - INSA - Institut National des Sciences Appliquées (France) StructId : 301232
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France) StructId : 300009
- CNRS - Centre National de la Recherche Scientifique (France) StructId : 441569
- UGA [2016-2019] - Université Grenoble Alpes [2016-2019] (38058 Grenoble cedex - France) StructId : 445543

2 LIFO - Laboratoire d'Informatique Fondamentale d'Orléans (Bâtiment IIIA, Rue Léonard de Vinci, B.P. 6759, F-45067 ORLEANS Cedex 2 - France) StructId : 241078

UO - Université d'Orléans : EA 4022 (Château de la Source - Avenue du Parc Floral - BP 6749 - 45067 Orléans cedex 2 - France) StructId : 300297
INSA CVL - Institut National des Sciences Appliquées - Centre Val de Loire : EA 4022 (88 boulevard Lahitolle, CS 60013, 18022 Bourges cedex - France) StructId : 303079
- INSA - Institut National des Sciences Appliquées (France) StructId : 301232

Document type :

Journal articles

Domain :

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

Complete list of metadata

https://hal.inria.fr/hal-01969498
Contributor : Accord Elsevier Ccsd Connect in order to contact the contributor
Submitted on : Thursday, October 21, 2021 - 9:44:25 PM
Last modification on : Wednesday, November 3, 2021 - 9:34:18 AM

File

S0166218X18303986.pdf

Files produced by the author(s)

Licence

Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License

Elsevier-hosted Accepted Manuscript

Identifiers

HAL Id : hal-01969498, version 1
PII : S0166-218X(18)30398-6
DOI : 10.1016/j.dam.2018.06.036

Collections

Citation

Christophe Crespelle, Anthony Perez, Ioan Todinca. An $O(n^2)$ time algorithm for the minimal permutation completion problem. Discrete Applied Mathematics, Elsevier, 2019, 254, pp.80-95. ⟨10.1016/j.dam.2018.06.036⟩. ⟨hal-01969498⟩

Export

BibTeX TEI DC DCterms EndNote

Metrics

Les métriques sont temporairement indisponibles

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

File

Licence

Identifiers

Collections

Citation

Export

Share

Metrics

Contact Legal Notice Personal Data