Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/11422/1986
Especie: | 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. |
Resumen: | 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. |
Materia: | Interseção de grafos Grade de interseção de grafos Programação inteira |
Materia CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
Unidade de producción: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
Es parte de: | Relatório Técnico NCE |
Número: | 2302 |
Fecha de publicación: | 31-dic-2002 |
País de edición : | Brasil |
Idioma de publicación: | eng |
Tipo de acceso : | Acesso Aberto |
Citación : | FAMPA,M. H. C. et al. Optimum grid representations. Rio de Janeiro: NCE, UFRJ, 2002. 12 p. (Relatório Técnico, 23/02) |
Aparece en las colecciones: | Relatórios |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
23_02_000613457.pdf | 212.76 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.