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 (v(1), v(2),....v(n)), such that any subgraph G(i)= G \ (v(1), v(2),, v(i)) with 1 &lt;= i &lt; n is isometric. This kind of ordering has been introduced by Chepoi in his study on weakly modular graphs (Chepoi, 1998). 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. (C) 2018 Elsevier B.V. All rights reserved.

On distance-preserving elimination orderings in graphs: Complexity and algorithms / D. Coudert, G. Ducoffe, N. Nisse, M. Soto Gomez. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 243:(2018 Jul 10), pp. 140-153. [10.1016/j.dam.2018.02.007]

### On distance-preserving elimination orderings in graphs: Complexity and algorithms

#### 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 (v(1), v(2),....v(n)), such that any subgraph G(i)= G \ (v(1), v(2),, v(i)) with 1 <= i < n is isometric. This kind of ordering has been introduced by Chepoi in his study on weakly modular graphs (Chepoi, 1998). 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. (C) 2018 Elsevier B.V. All rights reserved.
##### Scheda breve Scheda completa Scheda completa (DC)
Distance-preserving elimination ordering; Metric graph theory; NP-complete; Exact exponential algorithm; Integer linear programming; Bounded treewidth
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
10-lug-2018
Article (author)
File in questo prodotto:
File
1-s2.0-S0166218X18300520-main (1).pdf

accesso riservato

Descrizione: Article
Tipologia: Publisher's version/PDF
Dimensione 911.09 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/2434/961405`