The online graph bandwidth problem

DOI10.1016/0890-5401(92)90012-5zbMath0752.68060OpenAlexW2031103633MaRDI QIDQ1198951

Raymond Board

Publication date: 16 January 1993

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(92)90012-5

zbMATH Keywords

lower boundsonline algorithmgraph bandwidth problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive coloration of countable graphs
• A provably efficient algorithm for dynamic storage allocation
• Lower bounds for on-line two-dimensional packing algorithms
• The NP-completeness of the bandwidth minimization problem
• New Ressults on Server Problems
• Competitive algorithms for server problems
• On the Probable Performance of Heuristics for Bandwidth Minimization
• On-line and first fit colorings of graphs
• The Linearity of First-Fit Coloring of Interval Graphs
• New Algorithms for Bin Packing
• An Effective Version of Dilworth's Theorem
• Effective coloration

This page was built for publication: The online graph bandwidth problem