Discretization Orders for Distance Geometry Problems - Archive ouverte HAL Access content directly
Journal Articles Optimization Letters Year : 2012

Discretization Orders for Distance Geometry Problems

(1) , (2) , (3) , (4) , (5) , (3)
1
2
3
4
5

Abstract

Given a weighted, undirected simple graph G = (V,E,d) the Distance Geometry Problem (DGP) consists in determining an embedding x such that for each (i,j) in E ||xi - xj|| = d(i,j) . Although in general the DGP is solved using continuous methods, under certain conditions the search is reduced to a discrete set of points. We give one such condition as a particular order on V. We formalize the decision problem of determining whether such an order exists for a given graph and show that this problem is NP-complete in general and polynomial for fixed K. We exhibit computational experiments on a set of proteins whose natural atomic order does not satisfy the order requirements, and compare our approach with some available continuous space searches.

Dates and versions

hal-00756941 , version 1 (24-11-2012)

Identifiers

Cite

Antonio Mucherino, Carlile Lavor, Lee Jon, John Lee S., Leo Liberti, et al.. Discretization Orders for Distance Geometry Problems. Optimization Letters, 2012, 6 (4), pp.783-796. ⟨10.1007/s11590-011-0302-6⟩. ⟨hal-00756941⟩
437 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More