Cubicity and bandwidth

DOI10.1007/s00373-011-1099-xzbMath1258.05086MaRDI QIDQ1938886

Naveen Sivadasan, Mathew C. Francis, L. Sunil Chandran

Publication date: 25 February 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-011-1099-x

zbMATH Keywords

bandwidth; randomized algorithms; derandomization; geometric intersection graphs; cubicity

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Cubicity, degeneracy, and crossing number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the sphericity and cubicity of graphs
• Geometric representation of graphs in low dimension using axis parallel boxes
• Cubicity, boxicity, and vertex cover
• Cubicity of threshold graphs
• An upper bound for cubicity in terms of boxicity
• On the cubicity of certain graphs
• Sphericity exceeds cubicity for almost all complete bipartite graphs
• Optimal embedding of complete binary trees into lines and grids
• Label placement by maximum independent set in rectangles
• Sphere of influence graphs and the \(L_{\infty}\)-metric
• Sphericity, cubicity, and edge clique covers of graphs
• Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
• Cubicity of Interval Graphs and the Claw Number
• Domination on Cocomparability Graphs
• The Complexity of the Partial Order Dimension Problem
• On the Probable Performance of Heuristics for Bandwidth Minimization
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Graph-Theoretic Concepts in Computer Science