Complexity Results for Bandwidth Minimization
From MaRDI portal
Publication:4165413
DOI10.1137/0134037zbMath0385.05048OpenAlexW2162371997WikidataQ106434994 ScholiaQ106434994MaRDI QIDQ4165413
Donald E. Knuth, Michael R. Garey, David S. Johnson, Ronald L. Graham
Publication date: 1978
Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/53aa922f5575f6807da711845658807e053ec8a3
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items
On semidefinite programming bounds for graph bandwidth, Faster Exact Bandwidth, Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs, Graph layout problems, Tangle bases: Revisited, Approximating the bandwidth for asteroidal triple-free graphs, Computing $k$-Atomicity in Polynomial Time, Unnamed Item, Optimal arrangement of data in a tree directory, Bandwidth and topological bandwidth of graphs with few \(P_4\)'s, Decompositions into linear forests and difference labelings of graphs, The bandwidth problem and operations on graphs, The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete, Bandwidth of chain graphs, On the problem of bandsize, Matrix Relaxations in Combinatorial Optimization, Finding the minimum bandwidth of an interval graph, Bandwidth Minimization: An approximation algorithm for caterpillars, Mock threshold graphs, Parameterized power domination complexity, On bandwidth-2 graphs, Variable neighbourhood search for bandwidth reduction, Sequences of Radius k for Complete Bipartite Graphs, On bandwidth and edgesum for the composition of two graphs, Memory management optimization problems for integrated circuit simulators, On upper bounds of bandwidths of trees, Bounds on the convex label number of trees, On the complexity of loading shallow neural networks, 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, Restrictions of minimum spanner problems, Minimum degree conditions for the strength and bandwidth of graphs, Unnamed Item, Harper-type lower bounds and the bandwidths of the compositions of graphs, Lower bounds for the bandwidth problem, An extremal graph with given bandwidth, An exponential time 2-approximation algorithm for bandwidth, Helicopter search problems, bandwidth and pathwidth, Data encodings and their costs, Complexity and Algorithms for Well-Structured k-SAT Instances, The complexity of power indexes with graph restricted coalitions, An Application of Generalized Tree Pebbling to Sparse Matrix Factorization, Bandwidth of the composition of two graphs., Bandwidth of trees of diameter at most 4, A combinatorial optimization algorithm for solving the branchwidth problem, Routing with critical paths, A variation on the min cut linear arrangement problem, GRASP and path relinking for the matrix bandwidth minimization., The complexity of finding uniform emulations on paths and ring networks, Trimming of graphs, with application to point labeling, Bandwidth of the corona of two graphs, 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, Minimal cutwidth linear arrangements of abelian Cayley graphs, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, An improved simulated annealing algorithm for bandwidth minimization, 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, A study on cyclic bandwidth sum, Bandwidth of theta graphs with short paths, A note on the subgraphs of the (\(2\times \infty \))-grid, Sequences of radius \(k\) for complete bipartite graphs, The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete, A general strategy on the bandwidth minimization (BM) problem, On the complexity of tree embedding problems, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Exact and approximate bandwidth, Degree bounds for linear discrepancy of interval orders and disconnected posets, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, Exploiting structure in piecewise-linear homotopy algorithms for solving equations, On Harpers' Result Concerning the Bandwidths of Graphs, Bounds on mincut for Cayley graphs over Abelian groups, A simple linear-time algorithm for the recognition of bandwidth-2 biconnected graphs, Self‐clique graphs and matrix permutations, On minimizing width in linear layouts, On a pattern sequencing problem to minimize the maximum number of open stacks, Bandwidth contrained NP-complete problems, Computing Prüfer codes efficiently in parallel, 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 and pebbling, The minimization of open stacks problem: a review of some properties and their use in pre-processing operations, The achromatic number of bounded degree trees, Bandwidth and density for block graphs, On optimal linear arrangements of trees, On number of leaves and bandwidth of trees, Bandwidth constraints on problems complete for polynomial time, Embeddings of binary trees in lines, Combinatorial analysis (nonnegative matrices, algorithmic problems), On the Cutwidth and the Topological Bandwidth of a Tree, Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey, The bandwidth problem for distributive lattices of breadth 3, Counting Unlabelled Subtrees of a Tree is #P-complete, Edge Addition Number of Cartesian Product of Paths and Cycles, Complete problems for space bounded subclasses of NP, Myhill-Nerode Methods for Hypergraphs, Lattice bandwidth of random graphs, Topological Bandwidth, The Bandwidth of Caterpillars with Hairs of Length 1 and 2, Bandwidths and profiles of trees, Unnamed Item, Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time, On the bandwidth of the Kneser graph, Equitable colorings of bounded treewidth graphs
