On the Cutwidth and the Topological Bandwidth of a Tree

DOI10.1137/0606026zbMath0565.05019OpenAlexW2097333141MaRDI QIDQ3679205

Fan R. K. 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

treebandwidthtopological bandwidthcutwidthnumberinglinear arrangement

Mathematics Subject Classification ID

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

Related Items (20)

Minimal congestion trees ⋮ Decomposability of a class of \(k\)-cutwidth critical graphs ⋮ Bounds on the convex label number of trees ⋮ Min Cut is NP-complete for edge weighted trees ⋮ Graphs with small bandwidth and cutwidth ⋮ Perfect matching cuts partitioning a graph into complementary subgraphs ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Edge searching and fast searching with constraints ⋮ Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs ⋮ The cutwidth of trees with diameters at most 4 ⋮ Four-searchable biconnected outerplanar graphs ⋮ Partitioning a graph into complementary subgraphs ⋮ A degree sequence method for the cutwidth problem of graphs ⋮ A polynomial algorithm for recognizing bounded cutwidth in hypergraphs ⋮ Unnamed Item ⋮ The treewidth of line graphs ⋮ Edge searching weighted graphs ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Decompositions of critical trees with cutwidth \(k\) ⋮ Topological Bandwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The NP-completeness of the bandwidth minimization problem
• Some simplified NP-complete graph problems
• Topological Bandwidth
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• The bandwidth problem for graphs and matrices—a survey
• Complexity Results for Bandwidth Minimization

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