On the Probable Performance of Heuristics for Bandwidth Minimization

DOI10.1137/0215041MaRDI QIDQ3777452zbMATH OpenOpenAlexFDO

Authors Jonathan S. Turner

Publication date 1986

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

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

zbMATH Keywords

average-time algorithmsbandwidth minimizationbandwidth problemNP-hardpolynomial time

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding exact solutions to the bandwidth minimization problem
• A general strategy on the bandwidth minimization (BM) problem
• A branch and bound algorithm for the matrix bandwidth minimization
• A new matrix bandwidth reduction algorithm
• Exact and heuristic solutions to the bandwidth minimization problem

Cited in

(15)

• The online graph bandwidth problem
• Finding exact solutions to the bandwidth minimization problem
• GRASP and path relinking for the matrix bandwidth minimization.
• Approximating the bandwidth via volume respecting embeddings
• Vertex ordering and partitioning problems for random spatial graphs.
• Cubicity and bandwidth
• Lower bounds for the bandwidth problem
• The bandwidths of a matrix. A survey of algorithms
• Exact and heuristic solutions to the bandwidth minimization problem
• On the cubicity of AT-free graphs and circular-arc graphs
• Optimization Bounds from the Branching Dual
• Approximating the bandwidth for asteroidal triple-free graphs
• Bandwidth and profile minimization
• Bandwidth vs BFS width in matrix reordering, graph reconstruction, and graph drawing
• Lattice bandwidth of random graphs

This page was built for publication: On the Probable Performance of Heuristics for Bandwidth Minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3777452)