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

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-01393523
Contributor : Nicolas Nisse <>
Submitted on : Monday, November 7, 2016 - 5:34:56 PM
Last modification on : Thursday, November 14, 2019 - 5:38:06 PM
Long-term archiving on : Wednesday, February 8, 2017 - 2:30:14 PM

File

RR-8973.pdf
Files produced by the author(s)

Identifiers

  • 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-01393523v1⟩

Share

Metrics

Record views

497

Files downloads

153