6 papers
Minimum Spanning Trees for Square Crop Plots
Mingyang Gong, Adiesha Liyanage, Braeden Sopp +2
Motivated by accessing crop plots in a field, where each crop plot can only be visited by a given pair of entry/exit points (we have three different types, each having four cases),…
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 linearly…
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…
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…
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…