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

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	190-194
Number of pages	5
Journal	Discrete Applied Mathematics
Volume	267
DOIs	https://doi.org/10.1016/j.dam.2019.07.021
Publication status	Published - 31 Aug 2019

Keywords

Discretizable Molecular Distance Geometry Problem
Distance Geometry
Vertex orders

Access to Document

10.1016/j.dam.2019.07.021

Cite this

@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

UR - https://www.scopus.com/pages/publications/85071057226

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this