Graphs with small bandwidth and cutwidth

DOI10.1016/0012-365X(89)90083-6zbMath0668.05039MaRDI QIDQ1117949

P. D. Seymour, Fan R. K. Chung

Publication date: 1989

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

topological bandwidthcutwidthsmall bandwidth graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items

Minimal congestion trees, On upper bounds of bandwidths of trees, Approximating the bandwidth of caterpillars, Characterizations of \(k\)-cutwidth critical trees, The Firefighter Problem: A Structural Analysis, Strong SDP based bounds on the cutwidth of a graph, Hardness results for approximating the bandwidth, The theory of guaranteed search on graphs, On 3-cutwidth critical graphs, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, The Effect of Planarization on Width, The cutwidth of trees with diameters at most 4, The structure of graphs not admitting a fixed immersion, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Labeling schemes for weighted dynamic trees, The firefighter problem: further steps in understanding its complexity, Distortion lower bounds for line embeddings, Linear layouts measuring neighbourhoods in graphs, The Effect of Planarization on Width, Fixed-parameter algorithms for protein similarity search under mRNA structure constraints, Tree-width, path-width, and cutwidth, Multiplicity of finite graphs over the real line, Unnamed Item, 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, Approximating the bandwidth via volume respecting embeddings, Lower bounds on treespan, On number of leaves and bandwidth of trees

Cites Work

• Unnamed Item
• Graph minors. I. Excluding a forest
• The bandwidth problem and operations on graphs
• On the Cutwidth and the Topological Bandwidth of a Tree
• Topological Bandwidth
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• The bandwidth problem for graphs and matrices—a survey