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

treebandwidthpolynomial time algorithm

Mathematics Subject Classification ID

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

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

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

Cited in

(5)

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

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)