[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

The K-discretization and K-incident graphs for discretizable Distance Geometry

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

The Distance Geometry Problem (DGP) is the problem of determining whether a realization for a simple weighted undirected graph \(G=(V,E,d)\) in a given Euclidean space exists so that the distances between pairs of realized vertices u, \(v \in V\) correspond to the weights \(d_{uv}\), for each \(\{u,v\} \in E\). We focus on a special class of DGP instances, referred to as the Discretizable DGP (DDGP), and we introduce the K-discretization and the K-incident graphs for the DDGP class. The K-discretization graph is independent on the vertex order that can be assigned to V, and can be useful for discovering whether one of such orders actually exists so that the DDGP assumptions are satisfied. The use of a given vertex order allows the definition of another important graph, the K-incident graph, which is potentially useful for performing pre-processing analysis on the solution set of DDGP instances.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Alves, R., Lavor, C.: Geometric algebra to model uncertainties in the discretizable molecular distance geometry problem. Adv. Appl. Clifford Algebras 27, 439–452 (2017)

    Article  MathSciNet  Google Scholar 

  2. Gonçalves, D., Mucherino, A.: Optimal partial discretization orders for discretizable distance geometry. Int. Trans. Oper. Res. 23, 947–967 (2016)

    Article  MathSciNet  Google Scholar 

  3. Gonçalves, D., Mucherino, A., Lavor, C., Liberti, L.: Recent advances on the interval distance geometry problem. J. Global Optim. 69, 525–545 (2017)

    Article  MathSciNet  Google Scholar 

  4. Lavor, C., Lee, J., Lee-St.John, A., Liberti, L., Mucherino, A., Sviridenko, M.: Discretization orders for distance geometry problems. Optim. Lett. 6, 783–796 (2012)

    Article  MathSciNet  Google Scholar 

  5. Lavor, C., Liberti, L., Maculan, N., Mucherino, A.: The discretizable molecular distance geometry problem. Comput. Optim. Appl. 52, 115–146 (2012)

    Article  MathSciNet  Google Scholar 

  6. Lavor, C., Liberti, L., Mucherino, A.: The interval Branch-and-Prune algorithm for the discretizable molecular distance geometry problem with inexact distances. J. Global Optim. 56, 855–871 (2013)

    Article  MathSciNet  Google Scholar 

  7. Liberti, L., Lavor, C., Maculan, N.: A Branch-and-Prune algorithm for the molecular distance geometry problem. Int. Trans. Oper. Res. 15, 1–17 (2008)

    Article  MathSciNet  Google Scholar 

  8. Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. SIAM Rev. 56, 3–69 (2014)

    Article  MathSciNet  Google Scholar 

  9. Liberti, L., Lavor, C., Mucherino, A., Maculan, N.: Molecular distance geometry methods: from continuous to discrete. Int. Trans. Oper. Res. 18, 33–51 (2011)

    Article  MathSciNet  Google Scholar 

  10. Liberti, L., Masson, B., Lee, J., Lavor, C., Mucherino, A.: On the number of realizations of certain Henneberg graphs arising in protein conformation. Discrete Appl. Math. 165, 213–232 (2014)

    Article  MathSciNet  Google Scholar 

  11. Mucherino, A., Lavor, C., Liberti, L.: The discretizable distance geometry problem. Optim. Lett. 6, 1671–1686 (2012)

    Article  MathSciNet  Google Scholar 

  12. Mucherino, A., Lavor, C., Liberti, L.: Exploiting symmetry properties of the discretizable molecular distance geometry problem. J. Bioinform. Comput. Biol. 10(3), 1242009(1–15) (2012)

    Article  Google Scholar 

  13. Saxe J (1979) Embeddability of weighted graphs in \(k\)-space is strongly NP-hard. In: Proceedings of 17th Allerton conference in communications, control and computing, pp 480–489

Download references

Acknowledgements

We wish to thank the anonymous referees for the very fruitful comments. We are also grateful to the Brazilian research agencies FAPESP and CNPq for financial support.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Antonio Mucherino.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Abud, G., Alencar, J., Lavor, C. et al. The K-discretization and K-incident graphs for discretizable Distance Geometry. Optim Lett 14, 469–482 (2020). https://doi.org/10.1007/s11590-018-1294-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-018-1294-2

Keywords

Navigation