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 [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.
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01741277
Contributeur : David Coudert <>
Soumis le : jeudi 22 mars 2018 - 19:30:44
Dernière modification le : mercredi 10 octobre 2018 - 10:10:37
Document(s) archivé(s) le : jeudi 13 septembre 2018 - 01:34:02

Fichier

dpo-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

David Coudert, Guillaume Ducoffe, Nicolas Nisse, Mauricio Soto. On distance-preserving elimination orderings in graphs: Complexity and algorithms. Discrete Applied Mathematics, Elsevier, 2018, 243, pp.140-153. 〈10.1016/j.dam.2018.02.007〉. 〈hal-01741277〉

Partager

Métriques

Consultations de la notice

263

Téléchargements de fichiers

94