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

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 : 205728

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
- ENS Lyon - École normale supérieure - Lyon (15 parvis René Descartes - BP 7000 - 69342 Lyon Cedex 07 - France) StructId : 6818
- 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
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France) StructId : 300009
- Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France) StructId : 301088
- CNRS - Centre National de la Recherche Scientifique : UMR5668 (France) StructId : 441569
IXXI - Institut Rhône-Alpin des systèmes complexes (5, Rue du Vercors 69007 Lyon - France) StructId : 145352
- 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
- UJF - Université Joseph Fourier - Grenoble 1 (BP 53 - 38041 Grenoble Cedex 9 - France) StructId : 51016
- UJML - Université Jean Moulin - Lyon III (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

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 metadatas

https://hal.inria.fr/hal-01969498
Contributor : Christophe Crespelle <>
Submitted on : Friday, January 4, 2019 - 11:06:56 AM
Last modification on : Wednesday, November 20, 2019 - 3:27:06 AM

Identifiers

HAL Id : hal-01969498, version 1
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, 2018, pp.1-16. ⟨10.1016/j.dam.2018.06.036⟩. ⟨hal-01969498⟩

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

Identifiers

Collections

Citation

Export

Metrics

100

Contact

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

Identifiers

Collections

Citation

Export

Share

Metrics

100

Contact