Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges

DOI10.1016/j.endm.2010.05.050zbMath1237.68099OpenAlexW1974223105MaRDI QIDQ2883585

Celina M. Herrera de Figueiredo, Guilherme Dias da Fonseca, Raphael C. S. Machado, Vinícius G. Pereira de Sá

Publication date: 13 May 2012

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2010.05.050

zbMATH Keywords

algorithmgraphVLSINP-completepartial grid

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Cites Work

• The complexity of minimizing wire lengths in VLSI layouts
• Unit-length embedding of binary trees on a square grid
• The logic engine and the realization problem for nearest neighbor graphs
• Expansion of layouts of complete binary trees into grids
• The realization problem for Euclidean minimum spanning trees is NP-hard
• Unnamed Item
• Unnamed Item
• Unnamed Item