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

DOI10.1016/J.ENDM.2010.05.050MaRDI QIDQ2883585zbMATH OpenOpenAlexFDO

Authors Vinícius G. P. De Sá, Celina M. H. de Figueiredo, Guilherme D. Da Fonseca, R. C. S. Machado

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

graphalgorithmNP-completeVLSIpartial grid

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 139786
• scientific article; zbMATH DE number 3950392
• Complexity dichotomy on partial grid recognition
• The VLSI Complexity of Selected Graph Problems
• Class Steiner trees and VLSI-design

Cites work

• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• Expansion of layouts of complete binary trees into grids
• The complexity of minimizing wire lengths in VLSI layouts
• The logic engine and the realization problem for nearest neighbor graphs
• The realization problem for Euclidean minimum spanning trees is NP-hard
• The total chromatic number of some bipartite graphs.
• Unit-length embedding of binary trees on a square grid

Cited in

(4)

• On the maximum edge length in VLSI layouts of complete binary trees
• scientific article; zbMATH DE number 833244 (Why is no real title available?)
• scientific article; zbMATH DE number 88981 (Why is no real title available?)
• Complexity dichotomy on partial grid recognition

This page was built for publication: Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges

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