Delay optimization of linear depth Boolean circuits with prescribed input arrival times (Q866541)

We consider boolean circuits \(C\) over the basis \(\Omega=\{\lor,\land\}\) with inputs \(x_1, x_2,\ldots, x_n\) for which arrival times \(t_1,t_2,\ldots,t_n\in\mathbb{N}_0\) are given. For \(1\leq i\leq n\) we define the delay of \(x_i\) in \(C\) as the sum of \(t_i\) and the number of gates on a longest directed path in \(C\) starting at \(x_i\). The delay of \(C\) is defined as the maximum delay of an input. Given a function of the form \[ f(x_1,x_2,\ldots, x_n)=g_{n-1}(g_{n-2}(\ldots g_3(g_2(g_1(x_1,x_2),x_3),x_4),\ldots ),x_{n-1}),x_n) \] where \(g_j\in \Omega\) for \(1\leq j\leq n-1\) and arrival times for \(x_1,x_2,\ldots x_n\), we describe a cubic-time algorithm that determines a circuit for \(f\) over \(\Omega\) that is of linear size and whose delay is at most 1.44 times the optimum delay plus some small constant.