A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.

On Hamilton cycles in locally connected graphs with vertex degree constraints

It is shown that every connected, locally connected graph with the maximum vertex degree Δ(G)=5 and the minimum vertex degree δ(G)3 is fully cycle extendable. For Δ(G)4, all connected, locally connected graphs, including infinite ones, are explicitly described. The Hamilton Cycle problem for locally connected graphs with Δ(G)7 is shown to be NP-complete