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∖(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 (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.

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

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

Soto, M
2018

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∖(v1,v2,…,vi) with 1≤i
Articolo in rivista - Articolo scientifico
graph theory, metric
English
2018
243
140
153
reserved
Coudert, D., Ducoffe, G., Nisse, N., Soto, M. (2018). On distance-preserving elimination orderings in graphs: Complexity and algorithms. DISCRETE APPLIED MATHEMATICS, 243, 140-153 [10.1016/j.dam.2018.02.007].
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0166218X18300520-main (1).pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 911.09 kB
Formato Adobe PDF
911.09 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/220893
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
Social impact