On distance-preserving elimination orderings in graphs: complexity and algorithms
Artículo
Publication date
2018-07-10Metadata
Show full item record
Cómo citar
Coudert, David
Cómo citar
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.
Patrocinador
ANR project Stint
ANR-13-BS02-0007
ANR program "Investments for the Future"
ANR-11-LABX-0031-01
Inria associated team AIDyNet
Indexation
Artículo de publicación ISI
Quote Item
Discrete Applied Mathematics Volumen: 243 Páginas: 140-153
Collections
The following license files are associated with this item: