The NP-Completeness of the bandwidth minimization problem

No abstract is available for this paper.

• Publication year

  1976

• Venue

  Computing

• Publication date

  1976-09-01

• Fields of study

  Not labeled

• Identifiers
  DOI 10.1007/BF02280884
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• P-Complete Problems and Approximate Solutions

  1974cited by this paper
• Some simplified NP-complete problems

  1974cited by this paper
• The Design and Analysis of Computer Algorithms

  1974influential reference
• Minimizing the bandwidth of sparse symmetric matrices

  1973cited by this paper
• Note on minimizing the bandwidth of sparse, symmetric matrices

  1973cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• Several Strategies for Reducing the Bandwidth of Matrices

  1972influential reference
• Reducibility among combinatorial problems" in complexity of computer computations

  1972influential reference
• Reducing the bandwidth of sparse symmetric matrices

  1969cited by this paper

• DC-MBQC: A Distributed Compilation Framework for Measurement-Based Quantum Computing

  2026cites this paper
• A survey of heuristics for matrix bandwidth reduction

  2025cites this paper
• DiVerG: Scalable Distance Index for Validation of Paired-End Alignments in Sequence Graphs

  2025cites this paper
• Dyadic Factorization and Efficient Inversion of Sparse Positive Definite Matrices

  2025cites this paper
• Reductions in local certification

  2025cites this paper
• Exact and Approximate Digraph Bandwidth

  2025cites this paper
• Reinforcement learning driven heuristic for two-dimensional bandwidth minimization

  2025cites this paper
• Graphical house allocation with identical valuations

  2024cites this paper
• Parameterized Algorithms for Minimum Sum Vertex Cover

  2024cites this paper
• Solving unconstrained binary polynomial programs with limited reach: Application to low autocorrelation binary sequences

  2024cites this paper
• Arrow Matrix Decomposition: A Novel Approach for Communication-Efficient Sparse Matrix Multiplication

  2024cites this paper
• Ordering Transactions with Bounded Unfairness: Definitions, Complexity and Constructions

  2023cites this paper
• Schelling Games with Continuous Types

  2023cites this paper
• On the 2-Layer Window Width Minimization Problem

  2023cites this paper
• A Reduced Variable Neighbourhood Search Algorithm for Grid Bandwidth Minimization Problem

  2023cites this paper
• BOBA: A Parallel Lightweight Graph Reordering Algorithm with Heavyweight Implications

  2023cites this paper
• Improving Graph Generation by Restricting Graph Bandwidth

  2023cites this paper
• AN EVALUATION OF HEURISTIC METHODS FOR THE BANDWIDTH REDUCTION OF LARGE-SCALE GRAPHS

  2023cites this paper
• Fifty years of operational research: 1972-2022

  2023cites this paper
• Bandwidth Parameterized by Cluster Vertex Deletion Number

  2023cites this paper
• A Matrix-Free Newton Method

  2023cites this paper
• Graphical House Allocation

  2023cites this paper
• Minimizing running buffers for tabletop object rearrangement: Complexity, fast algorithms, and applications

  2023cites this paper
• Population-based iterated greedy algorithm for the S-labeling problem

  2023cites this paper
• Efficient large multibody flight dynamic simulation through improved nonlinear control constraint stabilization

  2023cites this paper
• On the solution of the graph bandwidth problem by means of search methods

  2022cites this paper
• Minimum degree conditions for the strength and bandwidth of graphs

  2022cites this paper
• Self-Adjusting Linear Networks with Ladder Demand Graph

  2022cites this paper
• Efficient iterated greedy for the two-dimensional bandwidth minimization problem

  2022cites this paper
• Speculative Parallel Reverse Cuthill-McKee Reordering on Multi- and Many-core Architectures

  2021cites this paper
• Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

  2021cites this paper
• Optimal patchings for consecutive ones matrices

  2021cites this paper
• Finding banded patternsin large data set using segmentation

  2021cites this paper
• Optimizing consolidation processes in hubs: The hub-arrival-departure problem

  2021cites this paper
• On Minimizing the Number of Running Buffers for Tabletop Rearrangement

  2021cites this paper
• On the Embed and Project Algorithm for the Graph Bandwidth Problem

  2021cites this paper
• Search Trajectory Networks Applied to the Cyclic Bandwidth Sum Problem

  2021cites this paper
• Low-cost heuristics for matrix bandwidth reduction combined with a Hill-Climbing strategy

  2021cites this paper
• Optimizing Sparse Matrix Storage for the Big Data Era

  2021cites this paper
• Enabling Exploratory Large Scale Graph Analytics through Arkouda

  2021cites this paper
• Metaheuristic algorithms for the bandwidth reduction of large-scale matrices

  2021cites this paper
• Efficient Message Passing for 0-1 ILPs with Binary Decision Diagrams

  2020influential citation
• Fast and efficient parallel breadth-first search with power-law graph transformation

  2020cites this paper
• Experiments with pseudoperipheral vertex finders for heuristics for bandwidth reduction evolved by an ant colony hyperheuristic approach

  2020cites this paper
• New Randomized Strategies for the Color Coding Algorithm

  2020cites this paper
• The Algorithm Design Manual

  2020influential citation
• A Biased Random-Key Genetic Algorithm for Bandwidth Reduction

  2020cites this paper
• Compact Representation of Graphs with Small Bandwidth and Treedepth

  2020influential citation
• 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, Tórshavn, Faroe Islands, June 22-24, 2020

  2020cites this paper
• An ant colony hyperheuristic approach for matrix bandwidth reduction

  2020cites this paper
• Distributed Phase Oscillatory Excitation Efficiently Produces Attractors Using Spike Timing Dependent Plasticity

  2020cites this paper
• Parameterized complexity of Bandwidth of Caterpillars and Weighted Path Emulation

  2020cites this paper
• Low-stretch spanning trees of graphs with bounded width

  2020cites this paper
• Long-Distance Dependencies Don’t Have to Be Long: Simplifying through Provably (Approximately) Optimal Permutations

  2019cites this paper
• Assignment problem with conflicts

  2019cites this paper
• Lower bounds for the bandwidth problem

  2019cites this paper
• Evolving reordering algorithms using an ant colony hyperheuristic approach for accelerating the convergence of the ICCG method

  2019cites this paper
• Um análise comparativa entre quatro algoritmos para reduções de largura de banda de matrizes

  2019cites this paper
• The Effect of Symmetric Permutations on the Convergence of a Restarted GMRES Solver with ILU-Type Preconditioners

  2019cites this paper
• Trees and graph packing Ph

  2018cites this paper
• Reordering Based Lossless Compression Scheme for Term-Document Matrices

  2018cites this paper
• Parallel Implementations of RCM Algorithm for Bandwidth Reduction of Sparse Matrices

  2018cites this paper
• A Modified Bandwidth Reduction Heuristic Based on the WBRA and George-Liu Algorithm

  2018cites this paper
• Redesign of the Solution Algorithms in Wanda

  2018cites this paper
• Computational improvements of a multibody dynamic simulation algorithm applied to a landing event simulation of a flexible legged Europa lander

  2018influential citation
• Finding a Starting Vertex for the Reverse Cuthill-McKee Method for Bandwidth Reduction: A Comparative Analysis Using Asymmetric Matrices

  2018cites this paper
• A Branch-and-Bound Algorithm for the Minimum Cost Bipartite Perfect Matching Problem with Conflict Pair Constraints

  2018cites this paper
• Mapping n Grid Points Onto a Square Forces an Arbitrarily Large Lipschitz Constant

  2018cites this paper
• An experimental analysis of Hager’s exchange methods in conjunction with heuristics for bandwidth and profile reductions applied to accelerate the ICCG method

  2018cites this paper
• A variant of Snay’s algorithm

  2018cites this paper
• An Assessment of Reordering Algorithms to Speed Up the ICCG Method Applied to CFD Problems

  2018cites this paper
• Alternative parameterizations of Metric Dimension

  2018cites this paper
• Metric and analytic methods

  2018cites this paper
• Biclustering Using Modified Matrix Bandwidth Minimization and Biogeography-based Optimization

  2018cites this paper
• Linear Layout Problems

  2018cites this paper
• Running Title : Profile and wavefront optimization by metaheuristic algorithms Profile and wavefront optimization by metaheuristic algorithms for efficient finite element analysis

  2018cites this paper
• Mapping n Grid Points Onto a Square Forces an Arbitrarily Large Lipschitz Constant

  2017cites this paper
• An Implementation of the Unordered Parallel RCM for Bandwidth Reduction of Large Sparse Matrices

  2017cites this paper
• Solving Graph Bandwidth Minimization Problem Using Imperialist Competitive Algorithm

  2017cites this paper
• Iterated exact and heuristic algorithms for the minimum cost bipartite perfect matching problem with conflict constraints

  2017cites this paper
• An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method

  2017cites this paper
• A GUIDED TABU SEARCH FOR PROFILE OPTIMIZATION OF FINITE ELEMENT MODELS

  2017cites this paper
• A non-speculative parallelization of reverse cuthill-McKee algorithm for sparse matrices reordering

  2017cites this paper
• An Analysis of Reordering Algorithms to Reduce the Computational Cost of the Jacobi-Preconditioned CG Solver Using High-Precision Arithmetic

  2017cites this paper
• An evaluation of four reordering algorithms to reduce the computational cost of the Jacobi-preconditioned conjugate gradient method using high-precision arithmetic

  2017cites this paper
• Relabelling vertices according to the network structure by minimizing the cyclic bandwidth sum

  2016cites this paper
• Lp-norm Regularization Algorithms for Optimization Over Permutation Matrices

  2016influential citation
• Memory Access Optimization for Computations on Unstructured Meshes

  2016cites this paper
• Banded Pattern Mining Algorithms in Multi-dimensional Zero-One Data

  2016cites this paper
• Bandwidth, Profile and Wavefront Optimization Using PSO, CBO, ECBO and TWO Algorithms

  2016cites this paper
• An evaluation of several heuristics for bandwidth and profile reductions to reduce the computational cost of the preconditioned Conjugate Gradient Method

  2016influential citation
• The Reverse Cuthill-McKee Algorithm in Distributed-Memory

  2016cites this paper
• An Optimized Leveled Parallel RCM for Bandwidth Reduction of Sparse Symmetric Matrices

  2016cites this paper
• An evaluation of low-cost heuristics for matrix bandwidth and profile reductions

  2016cites this paper
• Banded pattern mining for N-dimensional zero-one data

  2016cites this paper
• A survey of direct methods for sparse linear systems

  2016influential citation
• Graphs, Vectors, and Matrices

  2016cites this paper
• Bandwidth of Graphs Resulting from the Edge Clique Covering Problem

  2016cites this paper
• A New Heuristic for Bandwidth and Profile Reductions of Matrices Using a Self-organizing Map

  2016cites this paper
• A general resolution of intractable problems in polynomial time through DNA Computing

  2016cites this paper