Approximation algorithms for the a priori traveling repairman

Autor: Fatemeh Navidi, Inge Li Gørtz, Viswanath Nagarajan

Publikováno v: Navidi, F, Gørtz, I L & Nagarajan, V 2020, ' Approximation algorithms for the a priori traveling repairman ', Operations Research Letters, vol. 48, no. 5, pp. 599-606 . https://doi.org/10.1016/j.orl.2020.07.009

We consider the a priori traveling repairman problem, which is a stochastic version of the classic traveling repairman problem. Given a metric ( V , d ) with a root r ∈ V , the traveling repairman problem (TRP) involves finding a tour originating f

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::eefaa7b2a5acf2a05848a65b40f39a79
https://doi.org/10.1016/j.orl.2020.07.009

Random Access in Persistent Strings and Segment Selection

Autor: Inge Li Gørtz, Philip Bille

We consider compact representations of collections of similar strings that support random access queries. The collection of strings is given by a rooted tree where edges are labeled by an edit operation (inserting, deleting, or replacing a character)

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ba13f7198fdc1b657a6c91cd9e54a62f
http://arxiv.org/abs/2006.15575

Finger Search in Grammar-Compressed Strings

Autor: Inge Li Gørtz, Philip Bille, Patrick Hagge Cording, Anders Roy Christiansen

Publikováno v: Bille, P, Christiansen, A R, Cording, P H & Gørtz, I L 2016, Finger Search in Grammar-Compressed Strings . in Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) ., 36, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, vol. 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016), Chennai, India, 13/12/2016 . https://doi.org/10.4230/LIPIcs.FSTTCS.2016.36
Bille, P, Christiansen, A R, Cording, P H & Gørtz, I L 2018, ' Finger Search in Grammar-Compressed Strings ', Theory of Computing Systems, vol. 62, no. 8, pp. 1715-1735 . https://doi.org/10.1007/s00224-017-9839-9

Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures many popular compression schemes. Given a grammar, the random access problem is to

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::74b5758182a823f0872f15e1b11c4d98
https://doi.org/10.1007/s00224-017-9839-9

Subsequence automata with default transitions

Autor: Inge Li Gørtz, Philip Bille, Frederik Rye Skjoldjensen

Publikováno v: Bille, P, Gørtz, I L & Skjoldjensen, F R 2017, ' Subsequence automata with default transitions ', Journal of Discrete Algorithms, vol. 44, pp. 48-55 . https://doi.org/10.1016/j.jda.2017.05.001

Let $S$ be a string of length $n$ with characters from an alphabet of size $\sigma$. The \emph{subsequence automaton} of $S$ (often called the \emph{directed acyclic subsequence graph}) is the minimal deterministic finite automaton accepting all subs

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b20eeea91c2af2b4dd1660e4cbbd5d87
https://doi.org/10.1016/j.jda.2017.05.001

From regular expression matching to parsing

Autor: Inge Li Gørtz, Philip Bille

Publikováno v: Bille, P & Gørtz, I L 2019, From regular expression matching to parsing . in J-P Katoen, P Heggernes & P Rossmanith (eds), Proceedings of 44th International Symposium on Mathematical Foundations of Computer Science ., 71, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 138, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, Aachen, Germany, 26/08/2019 . https://doi.org/10.4230/LIPIcs.MFCS.2019.71

Given a regular expression $R$ and a string $Q$, the regular expression parsing problem is to determine if $Q$ matches $R$ and if so, determine how it matches, e.g., by a mapping of the characters of $Q$ to the characters in $R$. Regular expression p

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b092d4ca701a248f48a5af63435a5414
https://orbit.dtu.dk/en/publications/89964686-4d95-4c8f-9eff-61b4d3f38b01