Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/2582
Full metadata record
DC FieldValueLanguage
dc.contributor.authorFampa, M. H. C.-
dc.contributor.authorKlein, S.-
dc.contributor.authorProtti, F.-
dc.contributor.authorRêgo, D. C. A.-
dc.date.accessioned2017-08-04T11:07:24Z-
dc.date.available2017-08-06T03:00:15Z-
dc.date.issued2004-08-09-
dc.identifier.citationFampa, M. H. C., Klein, S., Protti, F. and Rêgo, D. C. A. (2004), Optimal grid representations. Networks, 44 (3): 187–193.pt_BR
dc.identifier.issn1097-0037pt_BR
dc.identifier.urihttp://hdl.handle.net/11422/2582-
dc.description.abstractA graph G is a grid intersection graph if G is the intersection graph of ℋ ∪ ℐ, where ℋ and ℐ are, respectively, finite families of horizontal and vertical linear segments in the plane such that no two parallel segments intersect. (This definition implies that every grid intersection graph is bipartite.) The family ℋ ∪ ℐ is a representation of G. As a consequence of a characterization of grid intersection graphs by Kratochvíl, we observe that when 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 × s)-grid for r = |U| and s = |W|, that is, a representation in which all end points of segments have integer-valued coordinates belonging to {(x, y) ∈ N × N | 1 ≤ y ≤ r, 1 ≤ x ≤ s} and the representative segment of each vertex lies on a distinct horizontal or vertical line. A natural problem, with potential applications to circuit layout, is the following: among all the possible normalized representations of G, find a representation ℛ such that the sum of the lengths of the segments in ℛ is minimum. In this work we introduce this problem and present a mixed integer programming formulation to solve it.en
dc.description.sponsorshipCNPqpt_BR
dc.description.sponsorshipFAPERJpt_BR
dc.languageengpt_BR
dc.publisherWiley Subscription Services, Inc., A Wiley Companyen
dc.relation.ispartofNetworkspt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectIntersection graph of segmentsen
dc.subjectGrid intersection graphen
dc.subjectGrid representationen
dc.subjectInteger programmingen
dc.titleOptimal grid representationsen
dc.typeArtigopt_BR
dc.identifier.doihttp://dx.doi.org/10.1002/net.20032pt_BR
dc.publisher.countryEstados Unidospt_BR
dc.publisher.departmentInstituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenhariapt_BR
dc.publisher.departmentInstituto Tércio Pacitti de Aplicações e Pesquisas Computacionaispt_BR
dc.subject.cnpqCNPQ::ENGENHARIAS::ENGENHARIA ELETRICA::TELECOMUNICACOESpt_BR
dc.citation.volume44pt_BR
dc.citation.issue3pt_BR
dc.citation.spage187pt_BR
dc.citation.epage193pt_BR
dc.embargo.termsabertopt_BR
Appears in Collections:Engenharias

Files in This Item:
File Description SizeFormat 
net20032.pdf212,76 kBAdobe PDFView/Open


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