A General Framework for Enumerating Equivalence Classes of Solutions

Autor: Yishu Wang, Arnaud Mary, Marie-France Sagot, Blerina Sinaimeri

Publikováno v: ESA 2021-29th Annual European Symposium on Algorithms
ESA 2021-29th Annual European Symposium on Algorithms, Sep 2021, Virtual, Portugal. pp.1-14, ⟨10.4230/LIPIcs.ESA.2021.80⟩

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5e987d15765a61f5c7370ad944dc5c24
https://doi.org/10.1007/s00453-023-01131-1

Dynamic Maintenance of Monotone Dynamic Programs and Applications

Autor: Henzinger, Monika, Neumann, Stefan, Räcke, Harald, Schmid, Stefan

Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3c64c4779bf3854a20cb475ea9207cca

Algorithms and Complexity on Indexing Elastic Founder Graphs

Autor: Equi, Massimo, Norri, Tuukka, Alanko, Jarno, Cazaux, Bastien, Tomescu, Alexandru I., M��kinen, Veli

Publikováno v: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

We study the problem of matching a string in a labeled graph. Previous research has shown that unless the Orthogonal Vectors Hypothesis (OVH) is false, one cannot solve this problem in strongly sub-quadratic time, nor index the graph in polynomial ti

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::54fb65c15f4d41920c731972214056b4
http://hdl.handle.net/10138/338450

Front Matter, Table of Contents, Preface, Conference Organization

Autor: Chechik, Shiri, Navarro, Gonzalo, Rotenberg, Eva, Herman, Grzegorz

Front Matter, Table of Contents, Preface, Conference Organization
LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 0:i-0:xxii

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::c19753a37740f965274159d7f92b57a5

Automated Design of Dynamic Programming Schemes for RNA Folding with Pseudoknots

Autor: Marchand, Bertrand, Will, Sebastian, Berkemer, Sarah J., Bulteau, Laurent, Ponty, Yann

Publikováno v: WABI 2022-22nd Workshop on Algorithms in Bioinformatics
WABI 2022-22nd Workshop on Algorithms in Bioinformatics, Sep 2022, Potsdam, Germany

Despite being a textbook application of dynamic programming (DP) and routine task in RNA structure analysis, RNA secondary structure prediction remains challenging whenever pseudoknots come into play. To circumvent the NP-hardness of energy minimizat

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::13beab5c2284cc29c7b8091f5e93ebf8