On the Cutwidth and the Topological Bandwidth of a Tree

DOI10.1137/0606026MaRDI QIDQ3679205zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

bandwidthcutwidthlinear arrangementnumberingtopological bandwidthtree

Mathematics Subject Classification ID

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

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\)

Cites work

• Complexity Results for Bandwidth Minimization
• scientific article; zbMATH DE number 3733986 (Why is no real title available?)
• scientific article; zbMATH DE number 3526692 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• Some simplified NP-complete graph problems
• The bandwidth problem for graphs and matrices—a survey
• The NP-completeness of the bandwidth minimization problem
• Topological Bandwidth

Cited in

(33)

• Edge searching weighted graphs
• Bounds on the convex label number of trees
• Min Cut is NP-complete for edge weighted trees
• Graphs with small bandwidth and cutwidth
• A partial k-arboretum of graphs with bounded treewidth
• On number of leaves and bandwidth of trees
• The cutwidth of trees with diameters at most 4
• Minimal congestion trees
• The bandwidth of a tree with \(k\) leaves is at most \(\lceil \frac k2 \rceil\)
• Weak-quasi-bandwidth and forward-bandwidth of graphs
• Decomposability of a class of \(k\)-cutwidth critical graphs
• Perfect matching cuts partitioning a graph into complementary subgraphs
• Four-searchable biconnected outerplanar graphs
• Decompositions of critical trees with cutwidth k
• Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs
• scientific article; zbMATH DE number 3857138 (Why is no real title available?)
• scientific article; zbMATH DE number 3858434 (Why is no real title available?)
• scientific article; zbMATH DE number 3914372 (Why is no real title available?)
• Topological Bandwidth
• scientific article; zbMATH DE number 3918388 (Why is no real title available?)
• A Linear Algorithm for Topological Bandwidth in Degree-Three Trees
• Cutwidth of triangular grids
• scientific article; zbMATH DE number 1760009 (Why is no real title available?)
• scientific article; zbMATH DE number 7559375 (Why is no real title available?)
• A polynomial algorithm for recognizing bounded cutwidth in hypergraphs
• Partitioning a graph into complementary subgraphs
• Edge-treewidth: algorithmic and combinatorial properties
• Edge searching and fast searching with constraints
• Tangled paths: a random graph model from Mallows permutations
• A degree sequence method for the cutwidth problem of graphs
• Perfect matching cuts partitioning a graph into complementary subgraphs
• The treewidth of line graphs
• Cut trees in the topological analysis of branching patterns

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)