Improved dynamic programming algorithms for bandwidth minimization and the MinCut linear arrangement problem. (English) Zbl 0556.68012

The dynamic programming algorithm of J. B. Saxe [SIAM J. Algebraic Discrete Methods 1, 363-369 (1980; Zbl 0496.68032)] for the bandwidth minimization problem is improved. It is shown that, for all \(k>1\), BANDWIDTH(k) can be solved in \(O(n^ k)\) steps and simultaneous \(O(n^ k)\) space, where n is the number of vertices in the graph, and that each such problem is in NSPACE(log n). The same improved dynamic programming algorithm approach works to show that the MINCUT LINEAR ARRANGEMENT problem restricted to the fixed value k, denoted by MINCUT(k), is solvable in \(O(n^ k)\) steps and simultaneous \(O(n^ k)\) space and is in the class NSPACE(log n).


68Q25 Analysis of algorithms and problem complexity
90C39 Dynamic programming


Zbl 0496.68032
Full Text: DOI