In this paper we consider the p-ary transitive reduction (TR_p) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. ... more >>>

We re-examine the complexity of evaluating monotone planar circuits
MPCVP, with special attention to circuits with cylindrical
embeddings. MPCVP is known to be in NC^3, and for the special
case of upward stratified circuits, it is known to be in
LogDCFL. We characterize cylindricality, which ... more >>>

We consider the non-uniform multicommodity buy-at-bulk network
design problem. In this problem we are given a graph $G(V,E)$ with
two cost functions on the edges, a buy cost $b:E\longrightarrow \RR^+$ and a rent cost
$r:E\longrightarrow\RR^+$, and a set of source-sink pairs $s_i,t_i\in V$ ($1\leq i\leq \alpha$)
with each pair $i$ ... more >>>