Bandwidth of trees of diameter at most 4

DOI10.1016/J.DISC.2012.03.006MaRDI QIDQ427848zbMATH OpenOpenAlexFDO

Authors Mark Bilinski, Kwang Ju Choi, Deborah Chun, Guoli Ding, Stan Dziobiak, Rodrigo Farnham, Perry Iverson, Shirley Leu, Lisa Warshauer Lowrance

Publication date 18 June 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2012.03.006

zbMATH Keywords

bandwidthpolynomial time algorithmtree

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

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

Cites work

• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• Complexity Results for Bandwidth Minimization
• scientific article; zbMATH DE number 3794093 (Why is no real title available?)
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• The bandwidth problem for graphs and matrices—a survey
• The Bandwidth Problem: critical Subgraphs and the Solution for Caterpillars

Cited in

(6)

• The bandwidth of the complement of a \(k\)-tree
• The cutwidth of trees with diameters at most 4
• The bandwidth of a tree with \(k\) leaves is at most \(\lceil \frac k2 \rceil\)
• scientific article; zbMATH DE number 3857138 (Why is no real title available?)
• Parameterized complexity of bandwidth on trees
• Bandwidth and topological bandwidth of graphs with few \(P_4\)'s

This page was built for publication: Bandwidth of trees of diameter at most 4

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