On the Probable Performance of Heuristics for Bandwidth Minimization

DOI10.1137/0215041zbMath0637.68050OpenAlexW2030470615MaRDI QIDQ3777452

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

NP-hardpolynomial timebandwidth problembandwidth minimizationaverage-time algorithms

Mathematics Subject Classification ID

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

Related Items (11)

Vertex ordering and partitioning problems for random spatial graphs. ⋮ Lower bounds for the bandwidth problem ⋮ Approximating the bandwidth for asteroidal triple-free graphs ⋮ Cubicity and bandwidth ⋮ Bandwidth and profile minimization ⋮ GRASP and path relinking for the matrix bandwidth minimization. ⋮ Optimization Bounds from the Branching Dual ⋮ The online graph bandwidth problem ⋮ On the Cubicity of AT-Free Graphs and Circular-Arc Graphs ⋮ Approximating the bandwidth via volume respecting embeddings ⋮ Lattice bandwidth of random graphs

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