Graphs with small bandwidth and cutwidth

DOI10.1016/0012-365X(89)90083-6MaRDI QIDQ1117949zbMATH OpenWikidataFDO

Authors Paul Seymour, Fan Chung

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(89)90083-6

zbMATH Keywords

cutwidthsmall bandwidth graphstopological bandwidth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Recommendations

• On the Cutwidth and the Topological Bandwidth of a Tree
• Topological Bandwidth
• scientific article; zbMATH DE number 3858434
• On bandwidth, cutwidth, and quotient graphs
• On minimizing width in linear layouts

Cites work

• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 3745191 (Why is no real title available?)
• On the Cutwidth and the Topological Bandwidth of a Tree
• The bandwidth problem and operations on graphs
• The bandwidth problem for graphs and matrices—a survey
• Topological Bandwidth
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees

Cited in

(38)

• Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
• Lower bounds on treespan
• On number of leaves and bandwidth of trees
• Skewness of graphs with small cutsets
• On 3-cutwidth critical graphs
• The cutwidth of trees with diameters at most 4
• 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
• Tree-width, path-width, and cutwidth
• Minimal congestion trees
• On upper bounds of bandwidths of trees
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Approximating the bandwidth of caterpillars
• Characterizations of \(k\)-cutwidth critical trees
• The theory of guaranteed search on graphs
• Labeling schemes for weighted dynamic trees
• Linear layouts measuring neighbourhoods in graphs
• The Firefighter Problem: A Structural Analysis
• Characterizing Graphs of Small Carving-Width
• Embedding spanning subgraphs of small bandwidth
• The effect of planarization on width
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• The structure of graphs not admitting a fixed immersion
• scientific article; zbMATH DE number 812088 (Why is no real title available?)
• scientific article; zbMATH DE number 1404133 (Why is no real title available?)
• The effect of planarization on width
• scientific article; zbMATH DE number 7236450 (Why is no real title available?)
• The firefighter problem: further steps in understanding its complexity
• Strong SDP based bounds on the cutwidth of a graph
• Hardness results for approximating the bandwidth
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
• Graph parameters, universal obstructions, and WQO
• Edge-maximal graphs with cutwidth at most three
• Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
• An overview of universal obstructions for graph parameters
• A coarse geometric approach to graph layout problems
• Multiplicity of finite graphs over the real line
• Distortion lower bounds for line embeddings

This page was built for publication: Graphs with small bandwidth and cutwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1117949)