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 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.
Complete list of metadatas

https://hal.inria.fr/hal-01393523
Contributor : Nicolas Nisse <>
Submitted on : Thursday, March 28, 2019 - 1:09:15 PM
Last modification on : Friday, March 29, 2019 - 2:47:23 AM

File

dpo_RR2019 (1).pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01393523, version 2

Collections

Citation

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⟩

Share

Metrics

Record views

86

Files downloads

57