2 citations · 4 across the 6 of their papers we have counts for
7 papers
Average-Case Subset Balancing Problems
Xi Chen, Yaonan Jin, Tim Randolph +1
Given a set of input integers, the Equal Subset Sum problem asks us to find two distinct subsets with the same sum. In this paper we present an algorithm that runs in time $O^*…
A Lower Bound on Cycle-Finding in Sparse Digraphs
Xi Chen, Tim Randolph, Rocco A. Servedio +1
We consider the problem of finding a cycle in a sparse directed graph that is promised to be far from acyclic, meaning that the smallest feedback arc set in is large. We pr…
(k,p)-Planarity: A Relaxation of Hybrid Planarity
Emilio Di Giacomo, William J. Lenhart, Giuseppe Liotta +2
We present a new model for hybrid planarity that relaxes existing hybrid representations. A graph is -planar if can be partitioned into clusters of size at m…
Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids
Timothy W. Randolph
Let be a graph and be positive integers. The \emph{signal} that a tower vertex of signal strength supplies to a vertex is defined as $sig(T,v)=max(t-dis…
Computing upper bounds for optimal density of broadcasts on the infinite grid
Benjamin F. Drews, Pamela E. Harris, Timothy W. Randolph
The domination number of a finite graph with vertex set is the cardinality of the smallest set such that for every vertex either or is…
Optimal Broadcasts On the Infinite Grid
Benjamin F. Drews, Pamela E. Harris, Timothy W. Randolph
Let be a graph and be positive integers. The signal that a vertex receives from a tower of signal strength located at vertex is defined as $sig(v,T)=max…