New methods for the Distance Geometry Problem

Gustavo Dias; Leo Liberti

doi:10.1016/j.endm.2016.10.012

New methods for the Distance Geometry Problem

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

Abstract

Given an integer K and a simple edge-weighted undirected graph G=(V,E), the Distance Geometry Problem questions the existence of a vertex realization function V→R^K such that each vertex pair adjacent to an edge is placed at a distance which is equal to the edge weight. This problem has many applications to science and engineering, and many methods have been proposed to solve it. We propose some new formulation-based methods.

Original language	English
Pages (from-to)	45-48
Number of pages	4
Journal	Electronic Notes in Discrete Mathematics
Volume	55
DOIs	https://doi.org/10.1016/j.endm.2016.10.012
Publication status	Published - 1 Nov 2016

Keywords

DGP
Diagonally dominant matrices
Semidefinite Programming

Access to Document

10.1016/j.endm.2016.10.012

Cite this

@article{2acc5b4533f2472eb8caf2cd0d3e28de,

title = "New methods for the Distance Geometry Problem",

abstract = "Given an integer K and a simple edge-weighted undirected graph G=(V,E), the Distance Geometry Problem questions the existence of a vertex realization function V→RK such that each vertex pair adjacent to an edge is placed at a distance which is equal to the edge weight. This problem has many applications to science and engineering, and many methods have been proposed to solve it. We propose some new formulation-based methods.",

keywords = "DGP, Diagonally dominant matrices, Semidefinite Programming",

author = "Gustavo Dias and Leo Liberti",

note = "Publisher Copyright: {\textcopyright} 2016",

year = "2016",

month = nov,

day = "1",

doi = "10.1016/j.endm.2016.10.012",

language = "English",

volume = "55",

pages = "45--48",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

}

TY - JOUR

T1 - New methods for the Distance Geometry Problem

AU - Dias, Gustavo

AU - Liberti, Leo

PY - 2016/11/1

Y1 - 2016/11/1

N2 - Given an integer K and a simple edge-weighted undirected graph G=(V,E), the Distance Geometry Problem questions the existence of a vertex realization function V→RK such that each vertex pair adjacent to an edge is placed at a distance which is equal to the edge weight. This problem has many applications to science and engineering, and many methods have been proposed to solve it. We propose some new formulation-based methods.

AB - Given an integer K and a simple edge-weighted undirected graph G=(V,E), the Distance Geometry Problem questions the existence of a vertex realization function V→RK such that each vertex pair adjacent to an edge is placed at a distance which is equal to the edge weight. This problem has many applications to science and engineering, and many methods have been proposed to solve it. We propose some new formulation-based methods.

KW - DGP

KW - Diagonally dominant matrices

KW - Semidefinite Programming

U2 - 10.1016/j.endm.2016.10.012

DO - 10.1016/j.endm.2016.10.012

M3 - Article

AN - SCOPUS:84995564825

SN - 1571-0653

VL - 55

SP - 45

EP - 48

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

New methods for the Distance Geometry Problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this