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

DOI10.1016/J.ENDM.2010.05.050zbMATH Open1237.68099OpenAlexW1974223105MaRDI QIDQ2883585FDOQ2883585

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

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

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)

Cites Work

• Title not available (Why is that?)
• The total chromatic number of some bipartite graphs.
• The realization problem for Euclidean minimum spanning trees is NP-hard
• 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
• Title not available (Why is that?)

Cited In (4)

• Complexity dichotomy on partial grid recognition
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the maximum edge length in VLSI layouts of complete binary trees

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)