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 (only showing first 100 items - show all)
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
This page was built for publication: Complexity Results for Bandwidth Minimization
