کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652754 | 1632595 | 2010 | 8 صفحه PDF | دانلود رایگان |
Deciding whether an arbitrary graph admits a VLSI layout with unit-length edges is NP-complete [Bhatt, S.N., and Cosmadakis, S.S., The complexity of minimizing wire lengths in VLSI layouts, Inform. Process. Lett. 25 (1987), 263–267], even when restricted to binary trees [Gregori, A., Unit-length embedding of binary trees on a square grid, Inform. Process. Lett. 31 (1989), 167–173]. However, for certain graphs, the problem is polynomial or even trivial. A natural step, outstanding thus far, was to provide a broader classification of graphs that make for polynomial or NP-complete instances. We provide such a classification based on the set of vertex degrees in the input graphs, yielding a comprehensive dichotomy on the complexity of the problem, with and without the restriction to trees.
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 391-398