License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.6
URN: urn:nbn:de:0030-drops-87035
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8703/
Go to the corresponding LIPIcs Volume Portal

Blin, Guillaume ; Blondin Massé, Alexandre ; Gasparoux, Marie ; Hamel, Sylvie ; Vandomme, Élise

Nearest constrained circular words

pdf-format:
LIPIcs-CPM-2018-6.pdf (0.6 MB)

Abstract

In this paper, we study circular words arising in the development of equipment using shields in brachytherapy. This equipment has physical constraints that have to be taken into consideration. From an algorithmic point of view, the problem can be formulated as follows: Given a circular word, find a constrained circular word of the same length such that the Manhattan distance between these two words is minimal. We show that we can solve this problem in pseudo polynomial time (polynomial time in practice) using dynamic programming.

BibTeX - Entry

@InProceedings{blin_et_al:LIPIcs:2018:8703,
  author =	{Guillaume Blin and Alexandre Blondin Mass{\'e} and Marie Gasparoux and Sylvie Hamel and {\'E}lise Vandomme},
  title =	{{Nearest constrained circular words}},
  booktitle =	{Annual Symposium on Combinatorial Pattern Matching  (CPM 2018)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Gonzalo Navarro and David Sankoff and Binhai Zhu},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8703},
  URN =		{urn:nbn:de:0030-drops-87035},
  doi =		{10.4230/LIPIcs.CPM.2018.6},
  annote =	{Keywords: Circular constrained alignments, Manhattan distance, Application to brachytherapy}
}

Keywords: Circular constrained alignments, Manhattan distance, Application to brachytherapy
Collection: Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Issue Date: 2018
Date of publication: 18.05.2018
Supplementary Material: A Haskell implementation of the algorithms discussed in this paper is available at https://gitlab.com/ablondin/nearest-constrained-circular-words

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI