Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges
From MaRDI portal
Publication:2883585
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
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