5 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…
Fast Order Statistics with Group Inequality Testing
Adiesha Liyanage, Brendan Mumey, Braeden Sopp
Suppose that a group test operation is available for checking order relations in a set, can this speed up problems like finding the minimum/maximum element, determining the rank of…
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…