On the polynomiality of finding KDMDGP re-orders

Carlile Lavor; Michael Souza; Luiz Mariano Carvalho; Leo Liberti

doi:10.1016/j.dam.2019.07.021

On the polynomiality of finding ^KDMDGP re-orders

Carlile Lavor
, Michael Souza
, Luiz Mariano Carvalho
, Leo Liberti

University of Campinas (UNICAMP)
Federal University of Ceara
Rua São Francisco de Xavier

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

In Cassioli et al. (2015), the complexity of finding ^KDMDGP re-orders was stated to be NP-complete by inclusion, which fails to provide a complete picture. In this paper we show that this problem is indeed NP-complete for K=1, but it is in P for each fixed K≥2.

langue originale	Anglais
Pages (de - à)	190-194
Nombre de pages	5
journal	Discrete Applied Mathematics
Volume	267
Les DOIs	https://doi.org/10.1016/j.dam.2019.07.021
état	Publié - 31 août 2019

Accès au document

10.1016/j.dam.2019.07.021

Contient cette citation

@article{8ed06f47350f40268f29009ba3e447ac,

title = "On the polynomiality of finding KDMDGP re-orders",

abstract = "In Cassioli et al. (2015), the complexity of finding KDMDGP re-orders was stated to be NP-complete by inclusion, which fails to provide a complete picture. In this paper we show that this problem is indeed NP-complete for K=1, but it is in P for each fixed K≥2.",

keywords = "Discretizable Molecular Distance Geometry Problem, Distance Geometry, Vertex orders",

author = "Carlile Lavor and Michael Souza and Carvalho, \{Luiz Mariano\} and Leo Liberti",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2019",

month = aug,

day = "31",

doi = "10.1016/j.dam.2019.07.021",

language = "English",

volume = "267",

pages = "190--194",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

}

TY - JOUR

T1 - On the polynomiality of finding KDMDGP re-orders

AU - Lavor, Carlile

AU - Souza, Michael

AU - Carvalho, Luiz Mariano

AU - Liberti, Leo

PY - 2019/8/31

Y1 - 2019/8/31

N2 - In Cassioli et al. (2015), the complexity of finding KDMDGP re-orders was stated to be NP-complete by inclusion, which fails to provide a complete picture. In this paper we show that this problem is indeed NP-complete for K=1, but it is in P for each fixed K≥2.

AB - In Cassioli et al. (2015), the complexity of finding KDMDGP re-orders was stated to be NP-complete by inclusion, which fails to provide a complete picture. In this paper we show that this problem is indeed NP-complete for K=1, but it is in P for each fixed K≥2.

KW - Discretizable Molecular Distance Geometry Problem

KW - Distance Geometry

KW - Vertex orders

U2 - 10.1016/j.dam.2019.07.021

DO - 10.1016/j.dam.2019.07.021

M3 - Article

AN - SCOPUS:85071057226

SN - 0166-218X

VL - 267

SP - 190

EP - 194

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

On the polynomiality of finding KDMDGP re-orders

Résumé

Accès au document

Empreinte digitale

Contient cette citation

On the polynomiality of finding ^KDMDGP re-orders