Distance-preserving orderings in graphs

David Coudert 1 Guillaume Ducoffe 1 Nicolas Nisse 1 Mauricio Soto 2
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : For every connected graph G, a subgraph H of G is isometric if for every two vertices x, y ∈ V (H) there exists a shortest xy-path of G in H. A distance-preserving elimination ordering of G is a total ordering of its vertex-set V (G), denoted (v1, v2,. .. , vn), such that any subgraph Gi = G \ (v1, v2,. .. , vi) with 1 ≤ i < n is isometric. This kind of ordering has been introduced by Chepoi in his study on weakly modular graphs. In this note we prove that it is NP-complete to decide whether such ordering exists for a given graph — even if it has diameter at most 2. Then, we describe a heuristic in order to compute a distance-preserving ordering when it exists one that we compare to an exact exponential algorithm and an ILP formulation for the problem. Lastly, we prove on the positive side that the problem of computing a distance-preserving ordering when it exists one is fixed-parameter-tractable in the treewidth.
Type de document :
[Research Report] RR-8973, Inria Sophia Antipolis. 2016
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

Contributeur : Nicolas Nisse <>
Soumis le : lundi 7 novembre 2016 - 17:34:56
Dernière modification le : mercredi 13 février 2019 - 18:30:03
Document(s) archivé(s) le : mercredi 8 février 2017 - 14:30:14


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01393523, version 1



David Coudert, Guillaume Ducoffe, Nicolas Nisse, Mauricio Soto. Distance-preserving orderings in graphs. [Research Report] RR-8973, Inria Sophia Antipolis. 2016. 〈hal-01393523〉



Consultations de la notice


Téléchargements de fichiers