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

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