Inmetro  >
Metrologia >
Metrologia Científica e Industrial >
Metrologia de Tecnologia da Informação e Comunicações >
DITEL | Artigos publicados em periódicos internacionais >

Please use this identifier to cite or link to this item:

Title: Complexity dichotomy on partial grid recognition
Authors: Sá, Vinícius Gusmão Pereira de
Fonseca, Guilherme Dias da
Machado, Raphael Carlos Santos
Figueiredo, Celina Miraglia Herrera de
Keywords: Teoria dos grafos
Processo de análise
Issue Date: 2011
Citation: SÁ, Vinícius G. P. de et al. Complexity dichotomy on partial grid recognition. Theoretical Computer Science, v. 412, p. 2370–2379, 2011.
Abstract: Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a number of graph classes for which the problem is polynomial, even trivial. A natural step, outstanding thus far, was to provide a broad classification of graphs that make for polynomial or NP-complete instances. We provide such a classification based on the set of allowed vertex degrees in the input graphs, yielding a full dichotomy on the complexity of the problem. As byproducts, the previous NP-completeness result for binary trees was strengthened to strictly binary trees, and the three-dimensional version of the problem was for the first time proven to be NP-complete. Our results were made possible by introducing the concepts of consistent orientations and robust gadgets, and by showing how the former allows NP-completeness proofs by local replacement even in the absence of the latter.
Description: 10 p. : il.
Document type: Artigo / Article
Unit: Divisão de Metrologia em Telecomunicações - Ditel
Appears in Collections:DITEL | Artigos publicados em periódicos internacionais

Files in This Item:

File Description SizeFormat
Sa_2011.pdf371,82 kBAdobe PDFUnder Embargo

This item is licensed under a Creative Commons License
Creative Commons

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2008  The DSpace Foundation - Feedback