Lower bounds on treespan

DOI10.1016/J.IPL.2005.06.001zbMATH Open1181.68178OpenAlexW2006854418MaRDI QIDQ1044709FDOQ1044709

Authors: Dieter Rautenbach 

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.06.001

Recommendations

• Graph searching, elimination trees, and a generalization of bandwidth
• Graph searching, elimination trees, and a generalization of bandwidth.
• Graph spanners
• scientific article; zbMATH DE number 434687
• Tree Spanners

zbMATH Keywords

bandwidthcombinatorial problemsdensity lower boundinert searchtreespan

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Optimal numberings and isoperimetric problems on graphs
• Bandwidth of the complete \(k\)-ary tree
• The bandwidth problem for graphs and matrices—a survey
• Graph searching, elimination trees, and a generalization of bandwidth
• Graphs with small bandwidth and cutwidth
• Bandwidth and pebbling

Cited In (7)

• A stronger lower bound on parametric minimum spanning trees
• Maximum vertex occupation time and inert fugitive: Recontamination does help
• Graph searching, elimination trees, and a generalization of bandwidth
• Lower-stretch spanning trees
• Graph searching, elimination trees, and a generalization of bandwidth.
• Transforming spanning trees: A lower bound
• A lower bound for tree resolution

This page was built for publication: Lower bounds on treespan

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