The NP-completeness of the bandwidth minimization problem
From MaRDI portal
Publication:1223124
DOI10.1007/BF02280884zbMath0321.65019OpenAlexW85690038MaRDI QIDQ1223124
Publication date: 1976
Published in: Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02280884
Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Graph theory (05C99) Direct numerical methods for linear systems and matrix inversion (65F05)
Related Items
On semidefinite programming bounds for graph bandwidth, Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs, Graph layout problems, Approximating the bandwidth for asteroidal triple-free graphs, Efficient iterated greedy for the two-dimensional bandwidth minimization problem, Population-based iterated greedy algorithm for the S-labeling problem, On the 2-layer window width minimization problem, Bandwidth and profile minimization, Computing $k$-Atomicity in Polynomial Time, Unnamed Item, A survey of direct methods for sparse linear systems, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Bandwidth of Bipartite Permutation Graphs in Polynomial Time, Self‐clique graphs and matrix permutations, Optimal Numberings of an $N \times N$ Array, A generalized insertion algorithm for the seriation problem, Optimal patchings for consecutive ones matrices, The bandwidth problem and operations on graphs, Regular codes in regular graphs are difficult, The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete, Bandwidth of chain graphs, Matrix Relaxations in Combinatorial Optimization, Metaheuristic algorithms for the bandwidth reduction of large-scale matrices, Finding the minimum bandwidth of an interval graph, Bandwidth Minimization: An approximation algorithm for caterpillars, Variable neighbourhood search for bandwidth reduction, Graphs, Vectors, and Matrices, Some parallel algorithms on interval graphs, On bandwidth and edgesum for the composition of two graphs, Estimating spatial covariance using penalised likelihood with weightedL1penalty, Particle swarm optimization and hill climbing for the bandwidth minimization problem, Heuristics for matrix bandwidth reduction, The complexity of minimizing wire lengths in VLSI layouts, Graph bandwidth of weighted caterpillars, Min Cut is NP-complete for edge weighted trees, Reducing the bandwidth of a sparse matrix with a genetic algorithm, Restrictions of minimum spanner problems, Minimum degree conditions for the strength and bandwidth of graphs, Unnamed Item, Characterizations and algorithmic applications of chordal graph embeddings, The maximum \(k\)-differential coloring problem, Harper-type lower bounds and the bandwidths of the compositions of graphs, Lower bounds for the bandwidth problem, The dominance assignment problem, An extremal graph with given bandwidth, 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, Data encodings and their costs, Hardness results for approximating the bandwidth, Complexity and Algorithms for Well-Structured k-SAT Instances, Bandwidth of the composition of two graphs., Linear arrangement problems on recursively partitioned graphs, Bandwidth of convex bipartite graphs and related graphs, A variation on the min cut linear arrangement problem, Complexity of representation of graphs by set systems, GRASP and path relinking for the matrix bandwidth minimization., Bandwidth on AT-free graphs, On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, A note on maximum differential coloring of planar graphs, On bandwidth, cutwidth, and quotient graphs, Bandwidth of the corona of two graphs, Tractabilities and intractabilities on geometric intersection graphs, Bandwidth of graphs resulting from the edge clique covering problem, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, A branch and bound algorithm for the matrix bandwidth minimization, Cyclic bandwidth with an edge added, An improved simulated annealing algorithm for bandwidth minimization, A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints, Approximation algorithms for the bandwidth minimization problem for a large class of trees, On bandwidth for the tensor product of paths and cycles, Optimal linear labelings and eigenvalues of graphs, Bandwidth of the strong product of two connected graphs, Bandwidth of theta graphs with short paths, Scheduling real-time computations with separation constraints, An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method, The online graph bandwidth problem, A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs, The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete, An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion, A general strategy on the bandwidth minimization (BM) problem, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Adaptive memory programming for matrix bandwidth minimization, Assignment problem with conflicts, On the edge-bandwidth of graph products, A Quartic Kernel for Pathwidth-One Vertex Deletion, An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion, Random Generation and Enumeration of Proper Interval Graphs, Mapping \(n\) grid points onto a square forces an arbitrarily large Lipschitz constant, An evaluation of low-cost heuristics for matrix bandwidth and profile reductions, Alternative parameterizations of \textsc{Metric Dimension}, SDP Relaxations for Some Combinatorial Optimization Problems, Linear layout of directed grid graph, The simultaneous consecutive ones problem, Bandwidth contrained NP-complete problems, GRASP with path relinking heuristics for the antibandwidth problem, $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices, Selected papers in honor of Manuel Blum on the occasion of his 60th birthday. Selected papers from the international conference in Theoretical Computer Science, Hong Kong, April 20-24, 1998, An Exponential Time 2-Approximation Algorithm for Bandwidth, Approximating the bandwidth via volume respecting embeddings, Bandwidth of bipartite permutation graphs in polynomial time, Bandwidth and pebbling, Bounding the bandwidths for graphs, Bandwidth and density for block graphs, Packing of (0, 1)-matrices, On optimal linear arrangements of trees, Bandwidth constraints on problems complete for polynomial time, On the Cutwidth and the Topological Bandwidth of a Tree, Edge Addition Number of Cartesian Product of Paths and Cycles, Complete problems for space bounded subclasses of NP, Topological Bandwidth, The Bandwidth of Caterpillars with Hairs of Length 1 and 2, Bandwidths and profiles of trees, Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time, On the bandwidth of the Kneser graph
Cites Work
