The online graph bandwidth problem

DOI10.1016/0890-5401(92)90012-5MaRDI QIDQ1198951zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The bandwidth problem and operations on graphs
• scientific article; zbMATH DE number 1186230
• scientific article; zbMATH DE number 3859182
• scientific article; zbMATH DE number 1617243
• scientific article; zbMATH DE number 2016615
• Bounding the bandwidths for graphs
• On the size of graphs of a given bandwidth
• A randomized online algorithm for bandwidth utilization
• scientific article; zbMATH DE number 2119708
• On bandwidth-2 graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3993569 (Why is no real title available?)
• A provably efficient algorithm for dynamic storage allocation
• An Effective Version of Dilworth's Theorem
• Competitive algorithms for server problems
• Effective coloration
• Lower bounds for on-line two-dimensional packing algorithms
• New Algorithms for Bin Packing
• New Ressults on Server Problems
• On the Probable Performance of Heuristics for Bandwidth Minimization
• On-line and first fit colorings of graphs
• Recursive coloration of countable graphs
• The Linearity of First-Fit Coloring of Interval Graphs
• The NP-completeness of the bandwidth minimization problem

Cited in

(3)

• Online promise problems with online width metrics
• scientific article; zbMATH DE number 2016615 (Why is no real title available?)
• Parameterized and Exact Computation

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

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