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
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 :
Rapport
[Research Report] RR-8973, Inria Sophia Antipolis. 2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01393523
Contributeur : Nicolas Nisse <>
Soumis le : lundi 7 novembre 2016 - 17:34:56
Dernière modification le : vendredi 9 décembre 2016 - 13:14:59
Document(s) archivé(s) le : mercredi 8 février 2017 - 14:30:14

Fichier

RR-8973.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01393523, version 1

Collections

Citation

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

Partager

Métriques

Consultations de
la notice

110

Téléchargements du document

95