On the Cutwidth and the Topological Bandwidth of a Tree

DOI10.1137/0606026zbMATH Open0565.05019OpenAlexW2097333141MaRDI QIDQ3679205FDOQ3679205

Authors: Fan Chung 

Publication date: 1985

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/339c851e597a00cfebf3d97e45529e403ad0ba09

Recommendations

• scientific article; zbMATH DE number 3858434
• Topological Bandwidth
• scientific article; zbMATH DE number 3914372
• A Linear Algorithm for Topological Bandwidth in Degree-Three Trees
• The bandwidth of a tree with \(k\) leaves is at most \(\lceil \frac k2 \rceil\)

zbMATH Keywords

treebandwidthnumberingcutwidthlinear arrangementtopological bandwidth

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Title not available (Why is that?)
• Some simplified NP-complete graph problems
• The NP-completeness of the bandwidth minimization problem
• Complexity Results for Bandwidth Minimization
• Topological Bandwidth
• The bandwidth problem for graphs and matrices—a survey
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (29)

• Title not available (Why is that?)
• Cutwidth of triangular grids
• Title not available (Why is that?)
• A polynomial algorithm for recognizing bounded cutwidth in hypergraphs
• A degree sequence method for the cutwidth problem of graphs
• Bounds on the convex label number of trees
• The cutwidth of trees with diameters at most 4
• Decomposability of a class of \(k\)-cutwidth critical graphs
• Min Cut is NP-complete for edge weighted trees
• A partial k-arboretum of graphs with bounded treewidth
• Four-searchable biconnected outerplanar graphs
• Decompositions of critical trees with cutwidth \(k\)
• Topological Bandwidth
• The treewidth of line graphs
• Minimal congestion trees
• Edge searching weighted graphs
• Cut trees in the topological analysis of branching patterns
• Edge-treewidth: algorithmic and combinatorial properties
• A Linear Algorithm for Topological Bandwidth in Degree-Three Trees
• Perfect matching cuts partitioning a graph into complementary subgraphs
• Graphs with small bandwidth and cutwidth
• Partitioning a graph into complementary subgraphs
• Title not available (Why is that?)
• The bandwidth of a tree with \(k\) leaves is at most \(\lceil \frac k2 \rceil\)
• Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Edge searching and fast searching with constraints
• Title not available (Why is that?)

This page was built for publication: On the Cutwidth and the Topological Bandwidth of a Tree

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