Distance-preserving orderings in graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2016

Distance-preserving orderings in graphs

Résumé

For every connected graph G, a subgraph H of G is isometric if the distance between any two vertices in H is the same in H as in G. 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 n (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 [11]. 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 prove on the positive side that the problem of computing a distance-preserving ordering when there exists one is fixed-parameter-tractable in the treewidth. Lastly, we describe a heuristic in order to compute a distance-preserving ordering when there exists one that we compare to an exact exponential time algorithm and to an ILP formulation for the problem.
Nous étudions les ordres d’élimination des sommets préservant les distances dans les graphes.
Fichier principal
Vignette du fichier
dpo_RR2019 (1).pdf (1.15 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01393523 , version 1 (07-11-2016)
hal-01393523 , version 2 (28-03-2019)

Identifiants

  • HAL Id : hal-01393523 , version 2

Citer

David Coudert, Guillaume Ducoffe, Nicolas Nisse, Mauricio Soto. Distance-preserving orderings in graphs. [Research Report] RR-8973, Inria Sophia Antipolis. 2016, pp.1-23. ⟨hal-01393523v2⟩
369 Consultations
356 Téléchargements

Partager

Gmail Facebook X LinkedIn More