Lower bounds on treespan

DOI10.1016/j.ipl.2005.06.001zbMath1181.68178OpenAlexW2006854418MaRDI QIDQ1044709

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

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)

Related Items (1)

Maximum vertex occupation time and inert fugitive: Recontamination does help

Cites Work

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

This page was built for publication: Lower bounds on treespan