4 papers
Parametric Shortest Paths in a Linearly Interpolated Graph
Jacob Sriraman, Eli Barton, Brittany Terese Fasy +6
We consider the parametric shortest paths problem in a linearly interpolated graph. Given two positively-weighted directed graphs and the linearl…
Computing and Enumerating Minimal Common Supersequences Between Two Strings
Braeden Sopp, Adiesha Liyanage, Mingyang Gong +1
Given \(k\) strings each of length at most , computing the shortest common supersequence of them is a well-known NP-hard problem (when \(k\) is unbounded). On the other hand, wh…
Computing Maximal Repeating Subsequences in a String
Mingyang Gong, Adiesha Liyanage, Braeden Sopp +1
In this paper we initiate the study of computing a maximal (not necessarily maximum) repeating pattern in a single input string, where the corresponding problems have been studied…
On the difficulty of order constrained pattern matching with applications to feature matching based malware detection
Adiesha Liyanage, Braeden Sopp, Binhai Zhu
We formulate low-level malware detection using algorithms based on feature matching as Order-based Malware Detection with Critical Instructions (General-OMDCI): given a pattern in…