On Some Variants of the Bandwidth Minimization Problem

DOI10.1137/0213040zbMath0545.68058OpenAlexW2092518753MaRDI QIDQ3335004

James D. Witthoff, Joseph Y.-T. Leung, O. Vornberger

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213040

zbMATH Keywords

multiprocessor schedulingdirected graphsNP-completeseparationinterval orderspolynomial time algorithmsforestsbandwidth minimizationlinear layoutcircular layoutcycle-bandwidthcycle-separationdirected separation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

Separation numbers of trees, Scheduling dyadic intervals, Computing the bump number with techniques from two-processor scheduling, Tabu search for the cyclic bandwidth problem, Fixed hypercube embedding, Algorithmic uses of the Feferman-Vaught theorem, The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues, The maximum \(k\)-differential coloring problem, Lower bounds for the bandwidth problem, Deep two-way matrix reordering for relational data analysis, Memetic algorithm for the antibandwidth maximization problem, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, Minimum gradation in greyscales of graphs, Population-based iterated greedy algorithm for the S-labeling problem, A special antidilation problem for meshes and Hamming graphs, The complexity of finding uniform emulations on paths and ring networks, Antibandwidth and cyclic antibandwidth of Hamming graphs, A note on maximum differential coloring of planar graphs, The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability, On circular layouts^∗, Cyclic bandwidth with an edge added, A metric approach for scheduling problems with minimizing the maximum penalty, Scheduling real-time computations with separation constraints, Antibandwidth of three-dimensional meshes, Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay., The complexity of graph languages generated by hyperedge replacement, A note on computational approaches for the antibandwidth problem, The connection between the bump number problem and flow-shop scheduling with precedence constraints, Contrast in greyscales of graphs, Antibandwidth and cyclic antibandwidth of meshes and hypercubes, On explicit formulas for bandwidth and antibandwidth of hypercubes, Level-based heuristics and hill climbing for the antibandwidth maximization problem, GRASP with path relinking heuristics for the antibandwidth problem, Optimizing consolidation processes in hubs: the hub-arrival-departure problem, Antibandwidth of complete \(k\)-ary trees, Antibandwidth and Cyclic Antibandwidth of Hamming Graphs, The Cyclic Antibandwidth Problem, Antibandwidth of Complete k-Ary Trees, Antibandwidth of Three-Dimensional Meshes, A general variable neighborhood search for the cyclic antibandwidth problem