Two models of two-dimensional bandwidth problems

DOI10.1016/j.ipl.2010.04.013zbMath1229.68058OpenAlexW1968798293MaRDI QIDQ656608

Lan Lin, Yanpei Liu

Publication date: 18 January 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.04.013

zbMATH Keywords

upper boundlower boundgraph algorithmsoptimal embeddingtwo-dimensional bandwidth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Efficient iterated greedy for the two-dimensional bandwidth minimization problem, Square-root rule of two-dimensional bandwidth problem

Cites Work

• Unnamed Item
• Unnamed Item
• VLSI layouts of complete graphs and star graphs
• A framework for solving VLSI graph layout problems
• The complexity of minimizing wire lengths in VLSI layouts
• Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
• The bandwidth problem for graphs and matrices—a survey
• The Bandwidth Problem: critical Subgraphs and the Solution for Caterpillars
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs