Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem

DOI10.1016/0196-6774(84)90006-3zbMath0556.68012OpenAlexW2084182003MaRDI QIDQ3219762

Eitan M. Gurari, Ivan Hal Sudborough

Publication date: 1984

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(84)90006-3

Mathematics Subject Classification ID

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

Related Items

Graph theoretic closure properties of the family of boundary NLC graph languages ⋮ Bandwidth of chain graphs ⋮ Finding the minimum bandwidth of an interval graph ⋮ Bandwidth Minimization: An approximation algorithm for caterpillars ⋮ Variable neighbourhood search for bandwidth reduction ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Efficient order processing in an inverse order picking system ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation} ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Graph layout problems ⋮ Cutwidth of triangular grids ⋮ Approximating the bandwidth for asteroidal triple-free graphs ⋮ Efficient iterated greedy for the two-dimensional bandwidth minimization problem ⋮ Bandwidth and profile minimization ⋮ Undecidability of the bandwidth problem on linear graph languages ⋮ Routing with critical paths ⋮ The complexity of finding uniform emulations on paths and ring networks ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ On bandwidth, cutwidth, and quotient graphs ⋮ An improved simulated annealing algorithm for bandwidth minimization ⋮ Approximation algorithms for the bandwidth minimization problem for a large class of trees ⋮ A note on the subgraphs of the (\(2\times \infty \))-grid ⋮ The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete ⋮ On the complexity of tree embedding problems ⋮ A polynomial algorithm for recognizing bounded cutwidth in hypergraphs ⋮ Bandwidth and topological bandwidth of graphs with few \(P_4\)'s ⋮ Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem ⋮ On minimizing width in linear layouts ⋮ Retracting Graphs to Cycles ⋮ Bandwidth contrained NP-complete problems ⋮ Linear graph grammars: Power and complexity ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ Approximating the bandwidth via volume respecting embeddings ⋮ Revising Johnson's table for the 21st century ⋮ Complete problems for space bounded subclasses of NP ⋮ Topological Bandwidth