The bandwidth problem for graphs and matrices—a survey
From MaRDI portal
Publication:3956994
DOI10.1002/jgt.3190060302zbMath0494.05057OpenAlexW2025902957WikidataQ50569546 ScholiaQ50569546MaRDI QIDQ3956994
Norman E. Gibbs, A. K. Dewdney, Jarmila Chvatalova, Phyllis Z. Chinn
Publication date: 1982
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.3190060302
Extremal problems in graph theory (05C35) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (05C99)
Related Items
A Result on the Strength of Graphs by Factorizations of Complete Graphs ⋮ Bandwidth Minimization: An approximation algorithm for caterpillars ⋮ Congestion optimale du plongement de l’hypercube $H (n)$ dans la chaîne $P(2^n)$ ⋮ On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ A spectral approach to bandwidth and separator problems in graphs ⋮ Approximating the bandwidth for asteroidal triple-free graphs ⋮ The Rique-number of graphs ⋮ Book embeddings and crossing numbers ⋮ Bandwidth and profile minimization ⋮ On bandwidth, cutwidth, and quotient graphs ⋮ An extremal bandwidth problem for bipartite graphs ⋮ Bandwidth and topological bandwidth of graphs with few \(P_4\)'s ⋮ Multilevel Bandwidth and Radio Labelings of Graphs ⋮ Unnamed Item ⋮ New bounds on the edge-bandwidth of triangular grids ⋮ A CHARACTERIZATION OF k-TH POWERS Pn,k OF PATHS IN TERMS OF k-TREES ⋮ Topological Bandwidth ⋮ Unnamed Item ⋮ Algorithms for the fixed linear crossing number problem ⋮ Decompositions into linear forests and difference labelings of graphs ⋮ Profile minimization problem for matrices and graphs ⋮ A parameterized complexity view on collapsing \(k\)-cores ⋮ The bandwidth problem and operations on graphs ⋮ New results on edge-bandwidth ⋮ The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete ⋮ On the problem of bandsize ⋮ 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 ⋮ Estimating spatial covariance using penalised likelihood with weightedL1penalty ⋮ On bandwidth sums of graphs ⋮ On upper bounds of bandwidths of trees ⋮ On the queue number of planar graphs ⋮ On embedding graphs in trees ⋮ Heuristics for matrix bandwidth reduction ⋮ Approximating the bandwidth of caterpillars ⋮ Graph bandwidth of weighted caterpillars ⋮ Edge-bandwidth of grids and tori ⋮ On the bandwidth of convex triangulation meshes ⋮ Minimum degree conditions for the strength and bandwidth of graphs ⋮ Unnamed Item ⋮ Characterizations and algorithmic applications of chordal graph embeddings ⋮ The mixed page number of graphs ⋮ Graphs with small bandwidth and cutwidth ⋮ The bandwidth of a tree with \(k\) leaves is at most \(\lceil \frac k2 \rceil\) ⋮ On the size of graphs of a given bandwidth ⋮ Harper-type lower bounds and the bandwidths of the compositions of graphs ⋮ Quasi-threshold graphs ⋮ Lower bounds for the bandwidth problem ⋮ An extremal graph with given bandwidth ⋮ Bandwidth and low dimensional embedding ⋮ Cutwidth of triangular grids ⋮ Helicopter search problems, bandwidth and pathwidth ⋮ Hardness results for approximating the bandwidth ⋮ Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ A bandwidth reduction algorithm for L-shaped and Z-shaped grid structured graphs ⋮ On the bandwidth of a Hamming graph ⋮ An improved upper bound on the queue number of planar graphs ⋮ Interval degree and bandwidth of a graph ⋮ Bandwidth of the composition of two graphs. ⋮ Bandwidth of trees of diameter at most 4 ⋮ On the monotonicity of games generated by symmetric submodular functions. ⋮ GRASP and path relinking for the matrix bandwidth minimization. ⋮ Algorithms for graphs with small octopus ⋮ Two models of two-dimensional bandwidth problems ⋮ Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity ⋮ Bandwidth of the corona of two graphs ⋮ Approximating the fixed linear crossing number ⋮ Thread Graphs, Linear Rank-Width and Their Algorithmic Applications ⋮ New classes of extremal graphs with given bandwidth ⋮ 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 ⋮ Labeling schemes for weighted dynamic trees ⋮ 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 ⋮ Bandwidth of theta graphs with short paths ⋮ On the bandwidth of 3-dimensional Hamming graphs ⋮ Sequences of radius \(k\) for complete bipartite graphs ⋮ The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete ⋮ Bandwidth and pathwidth of three-dimensional grids ⋮ A general strategy on the bandwidth minimization (BM) problem ⋮ A degree sequence method for the cutwidth problem of graphs ⋮ A characterisation of posets that are nearly antichains ⋮ An analysis of some linear graph layout heuristics ⋮ Degree bounds for linear discrepancy of interval orders and disconnected posets ⋮ On the edge-bandwidth of graph products ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ On Harpers' Result Concerning the Bandwidths of Graphs ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ The profile of the Cartesian product of graphs ⋮ On the domination search number ⋮ Investigation of the structure of binary variables ⋮ Bandwidth and Low Dimensional Embedding ⋮ On explicit formulas for bandwidth and antibandwidth of hypercubes ⋮ On width measures and topological problems on semi-complete digraphs ⋮ On the profile of the corona of two graphs ⋮ Bandwidth contrained NP-complete problems ⋮ $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices ⋮ Linear graph grammars: Power and complexity ⋮ 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 ⋮ Parallel multigrid preconditioning of the conjugate gradient method for systems of subsurface hydrology ⋮ Approximating the bandwidth via volume respecting embeddings ⋮ Lower bounds on treespan ⋮ Square-root rule of two-dimensional bandwidth problem ⋮ The minimization of open stacks problem: a review of some properties and their use in pre-processing operations ⋮ Bounding the bandwidths for graphs ⋮ Bandwidth and density for block graphs ⋮ On number of leaves and bandwidth of trees ⋮ Bandwidth constraints on problems complete for polynomial time ⋮ A new matrix bandwidth reduction algorithm ⋮ On the Cutwidth and the Topological Bandwidth of a Tree ⋮ Edge Addition Number of Cartesian Product of Paths and Cycles ⋮ Packing trees into planar graphs
Cites Work
