6 papers · 1 filter
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),…
Approximation Algorithms for Perfect Fair-Triangle Packing
Mingyang Gong, Zhi-Zhong Chen, Brendan Mumey
In this paper, we study the {\em perfect fair-triangle packing} problem (abbreviated as PFTP), which incorporates the fairness criterion from {\em fair clustering} into the {\em ma…
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…
Offline green bin packing and its constrained variant
Mingyang Gong, Brendan Mumey
In this paper, we study the {\em green bin packing} (GBP) problem where and are two given values as part of the input. The energy consumed by a bin is $\max…
Approximately Partitioning Vertices into Short Paths
Mingyang Gong, Zhi-Zhong Chen, Brendan Mumey
Given a fixed positive integer and a simple undirected graph , the {\em -path partition} problem, denoted by PP for short, aims to find a minimum collection…
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…