Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/1986
Tipo: Relatório
Título: Optimum grid representations
Autor(es)/Inventor(es): Fampa, Márcia Helena Costa
Klein, S.
Protti, Fábio
Rêgo, D. C. A.
Resumo : A graph G is a grid intersection graph if G is the intersection graph of H U I, where H and I are, respectively, finite families of horizontal and vertical linear segments in the plane such that do two parallel segments intersect. (This definition implies that every grid intersection graph is bipartite.) Any family of segments realizing G is a representation of G. As a consequence of a characterization of grid intersection graphs by Kratochvíl [7], we observe that a bipartite graph G = (U ᵁ W, E) with minimum degree at least two is a grid intersection graph, then there exists a normalized representation of G on the (r X s)-grid, where r = |U| and s = |W|. A natural problem, with potential applications to circuit layout, is the following: among all the possible representations of G on the (r x s)-grid, find a representation R such that the sum of the lenghts of the segments in R is minimum. In this work we introduce this problem and present a mixed integer programming formulation to solve it.
Palavras-chave: Interseção de grafos
Grade de interseção de grafos
Programação inteira
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Número: 2302
Data de publicação: 31-Dez-2002
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: FAMPA,M. H. C. et al. Optimum grid representations. Rio de Janeiro: NCE, UFRJ, 2002. 12 p. (Relatório Técnico, 23/02)
URI: http://hdl.handle.net/11422/1986
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
23_02_000613457.pdf212,76 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.