Cubicity and bandwidth

DOI10.1007/S00373-011-1099-XMaRDI QIDQ1938886zbMATH OpenOpenAlexFDO

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

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

bandwidthrandomized algorithmsderandomizationgeometric intersection graphscubicity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• On the cubicity of AT-free graphs and circular-arc graphs
• On the Cubicity of Interval Graphs
• On the cubicity of interval graphs
• On the cubicity of bipartite graphs
• The cubicity of hypercube graphs

Cites work

• scientific article; zbMATH DE number 1696538 (Why is no real title available?)
• scientific article; zbMATH DE number 1775392 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• An upper bound for cubicity in terms of boxicity
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Complexity results on graphs with few cliques
• Cubicity of interval graphs and the claw number
• Cubicity of threshold graphs
• Cubicity, boxicity, and vertex cover
• Domination on Cocomparability Graphs
• Efficient approximation algorithms for tiling and packing problems with rectangles
• Geometric representation of graphs in low dimension using axis parallel boxes
• Graph-Theoretic Concepts in Computer Science
• Label placement by maximum independent set in rectangles
• On the Probable Performance of Heuristics for Bandwidth Minimization
• On the cubicity of certain graphs
• On the sphericity and cubicity of graphs
• Optimal embedding of complete binary trees into lines and grids
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Sphere of influence graphs and the \(L_{\infty}\)-metric
• Sphericity exceeds cubicity for almost all complete bipartite graphs
• Sphericity, cubicity, and edge clique covers of graphs
• The Complexity of the Partial Order Dimension Problem

Cited in

(7)

• Cubicity, degeneracy, and crossing number
• On the cubicity of interval graphs
• On the Cubicity of Interval Graphs
• On the cubicity of bipartite graphs
• Bandwidth and pathwidth of three-dimensional grids
• A study of frequency cubes
• On the cubicity of AT-free graphs and circular-arc graphs

This page was built for publication: Cubicity and bandwidth

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