Geodesic
Vertex order with optimal number of adjacent predecessors
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1.

Voir la notice de l'article provenant de la source Episciences

In this paper, we study the complexity of the selection of a graph discretization order with a stepwise linear cost function. Finding such vertex ordering has been proved to be an essential step to solve discretizable distance geometry problems (DDGPs). DDGPs constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. In particular, it is useful to find discretization orders that minimize an indicator of the size of the search tree. Our stepwise linear cost function generalizes this situation and allows to discriminate the vertices into three categories depending on the number of adjacent predecessors of each vertex in the order and on two parameters K and U. We provide a complete study of NP-completeness for fixed values of K and U. Our main result is that the problem is NP-complete in general for all values of K and U such that U ≥ K + 1 and U ≥ 2. A consequence of this result is that the minimization of vertices with exactly K adjacent predecessors in a discretization order is also NP-complete.
DOI : 10.23638/DMTCS-22-1-1
Classification : 05C10, 05C12 
@article{DMTCS_2020_22_1_a1,
     author = {Omer, J\'er\'emy and Migot, Tangi},
     title = {Vertex order with optimal number of adjacent predecessors},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-1-1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-1/}
}
TY  - JOUR
AU  - Omer, Jérémy
AU  - Migot, Tangi
TI  - Vertex order with optimal number of adjacent predecessors
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-1/
DO  - 10.23638/DMTCS-22-1-1
LA  - en
ID  - DMTCS_2020_22_1_a1
ER  - 
%0 Journal Article
%A Omer, Jérémy
%A Migot, Tangi
%T Vertex order with optimal number of adjacent predecessors
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-1/
%R 10.23638/DMTCS-22-1-1
%G en
%F DMTCS_2020_22_1_a1
Omer, Jérémy; Migot, Tangi. Vertex order with optimal number of adjacent predecessors. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi : 10.23638/DMTCS-22-1-1. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-1/

Cité par Sources :