An Approximation Algorithm for Diagnostic Test Scheduling in Multicomputer Systems

The problem of diagnostic test scheduling (DTS) is to assign to each edge e of a diagnostic graph G a time interval of length l(e) so that intervals corresponding to edges at any given vertex do not overlap and the overall finishing time is minimum. In this correspondence we show that the DTS problem is NP-complete. Then we present a longest, first sequential scheduling algorithm which runs in worst case time O(dm log n) and uses O(m) space to produce a solution of length less than four times optimal. Then we show that the general performance bound can be strengthened to 3 * OPT(G) for low-degree graphs and to 2 ·OPT(G) in some special cases of binomial diagnostic graphs.