11 |
Um mecanismo de provisionamento de tráfego para serviços diferenciadosPacifico de Moura Neto, José January 2003 (has links)
Made available in DSpace on 2014-06-12T15:58:48Z (GMT). No. of bitstreams: 2
arquivo4709_1.pdf: 597732 bytes, checksum: 06d38a78dbd04d2e94a458df7336670d (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2003 / Podemos verificar que o modelo de melhor esforço não é adequado
para atender as necessidades das novas aplicações avançadas na rede.
Para melhor disponibilizar estas aplicações é necessário a inclusão de
qualidade de serviço como forma de oferecer garantias de desempenho.
Algumas arquiteturas vêm sendo desenvolvidas como forma de oferecer
garantias de QoS fim a fim, entre elas [1][13][25]. Dentre estas, a Arquitetura
Chameleon se destaca apresentando um modelo inovador de negociação
hierárquica de serviços. Dentre os planos da arquitetura Chameleon, faz-se
necessário implementar um mecanismo de monitoramento e controle,
atuando no plano de operação, com roteadores e tráfego real, avaliando e
configurando o provisionamento de tráfego, complementando a arquitetura.
Assim, neste trabalho implementamos um mecanismo de provisionamento de
tráfego, dentre os modelos que implementam QoS [33]. O modelo de serviços
escolhido foi o modelo de serviços diferenciados, definido pela IETF,
provendo escalabilidade de diferenciação de serviços na Internet
|
12 |
Binarização de imagens de documentos utilizando estimativa local de largura de traçoALMEIDA, Leandro Henrique Espindola Viana de 03 August 2015 (has links)
Submitted by Bárbara Carmo (barbara.queirozcarmo@ufpe.br) on 2018-11-23T21:24:08Z
No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
DISSERTAÇÃO Leandro Henrique Espindola V de Almeida.pdf: 12354898 bytes, checksum: e501e3b7bee62acb68e2235e19c27bf8 (MD5) / Rejected by Alice Araujo (alice.caraujo@ufpe.br), reason: on 2018-11-23T21:48:10Z (GMT) / Submitted by Bárbara Carmo (barbara.queirozcarmo@ufpe.br) on 2018-11-23T21:51:06Z
No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
DISSERTAÇÃO Leandro Henrique Espindola V de Almeida.pdf: 12354898 bytes, checksum: e501e3b7bee62acb68e2235e19c27bf8 (MD5) / Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-11-23T21:57:45Z (GMT) No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
DISSERTAÇÃO Leandro Henrique Espindola V de Almeida.pdf: 12354898 bytes, checksum: e501e3b7bee62acb68e2235e19c27bf8 (MD5) / Made available in DSpace on 2018-11-23T21:57:45Z (GMT). No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
DISSERTAÇÃO Leandro Henrique Espindola V de Almeida.pdf: 12354898 bytes, checksum: e501e3b7bee62acb68e2235e19c27bf8 (MD5)
Previous issue date: 2015-08-03 / Este trabalho apresenta um novo método de binarização para imagens de documentos. O algoritmo proposto utiliza operações morfológicas, estimativas de background, estimativas de largura de traço e imagens de contraste para realizar a classificação dos pixels. A estratégia de estimativa da largura de traço também é uma novidade proposta por este trabalho, desenvolvida a partir de análises de outras estratégias utilizadas na literatura e disposta a suprir deficiências identificadas nessas outras metodologias. O algoritmo foi avaliado a partir dos critérios utilizados em competições internacionais de binarização de imagens de documentos, e seu desempenho foi comparado com outras técnicas clássicas e recentes, escolhidas de acordo com a semelhança de suas estratégias em relação à técnica aqui proposta. Todas as imagens utilizadas no trabalho possuem um padrão ouro – ground truth – associado, para aferição dos resultados. A qualidade da estimativa da largura de traço também foi analisada junto a outras formas de estimativa encontradas nos algoritmos utilizados nos experimentos. A análise geral dos resultados demonstra que o algoritmo apresentou melhor desempenho em imagens de documentos manuscritos, e um desempenho compatível com os demais quando atuando sobre imagens de documentos tipografados. A estimativa da largura de traço apresentou desempenho superior às demais estratégias utilizadas na comparação. A partir dos resultados, foi feita uma análise de caso, identificando pontos fortes e deficiências do algoritmo proposto, e possíveis aprimoramentos são sugeridos, no intuito de dar continuidade aos estudos nessa área, seguindo com o desenvolvimento da técnica para obtenção de melhores resultados. / This paper proposes a new binarization method for document images. The proposed algorithm uses morphological operations, background estimation, stroke width estimation and contrast images to perform pixel classification. The strategy for estimating the stroke width is also a new proposal of this work, developed from studies of other strategies used in the literature and willing to meet shortcomings identified in these other methodologies. The algorithm was evaluated based on criteria used in international competitions of document images binarization, and its performance was compared to other classic and recent techniques, chosen according to the similarity of their strategies regarding the technique described. All images used in this study have a ground truth image associated, for measuring the results. The quality of the estimated stroke width was also evaluated alongside with other forms of estimations found in the literature. Overall results show that the algorithm performed better with the handwritten document images, and it has a compatible performance compared to others, acting on typewritten document images. The stroke width estimation method has superior performance to other strategies used in the comparison. From the results, a case study was made, identifying strengths and weaknesses of the proposed algorithm, and possible solutions are proposed in order to continue their studies in this area, following the development of the technique for better results.
|
13 |
Avaliação do posicionamento de caninos superiores permanentes na fase da dentadura mista em relação à largura do arco dentário e ao espaço na região anterior / Evaluation of the maxillary canines position in mixed-dentition and width and anterior space relationshipSuga, Selma Sano 19 March 2008 (has links)
Este estudo avaliou o posicionamento de caninos superiores permanentes em relação à largura do arco dentário superior e ao espaço na região anterior em pacientes na fase da dentadura mista. Foram analisados radiografias panorâmicas e modelos de estudo pré-tratamento de pacientes sem caninos deslocados (n = 68; 34 do gênero masculino; 34 do gênero feminino). A amostra foi dividida em idade e gênero. A largura do arco dentário e o espaço na região anterior entre os incisivos permanentes foram medidos. A posição e a inclinação do canino na radiografia panorâmica foram avaliadas em relação à linha mediana. Os resultados deste estudo mostram que não houve diferenças no posicionamento dos caninos permanentes em relação às variáveis analisadas. A média da angulação do canino superior em relação à linha mediana foi 6,2o e 10o para o gênero feminino e 9,2o e 11o para o masculino, respectivamente para o lado direito e esquerdo. / This study investigated the correlation between maxillary dental arch width, anterior space and the position of canines in patients during the mixed-dentition stage. Pretreatment Panoramic radiographs and dental casts were evaluated of randomly selected patients in the mixed dentition without maxillary canines displaced (n = 68; male, 34; female, 34). This sample was matched according to sex and age. Arch widths between the maxillary canines deciduous and anterior space between permanent incisors were measured and recorded. The position and inclination of canine on panoramic radiography was investigated. The results of this study showed that there are similarities in the position of the permanent canines in all cases and in both gender. The average of the canine\'s angulation to the mid-sagital plane was 6,2o and 10o for female and 9,2o and 11o for male, respectively to the right and left side.
|
14 |
"Estudo comparativo da largura dos dentes naturais anteriores superiores em ralação aos dentes artificiais para prótese total" / Comparative study between upper anterior natural teeth and artificial teeth for complete denturesKiausinis, Max Dalla 14 September 2005 (has links)
Estudou-se a largura dos dentes anteriores superiores de 121 jovens universitários brasileiros para determinar quais modelos e qual marca de dentes artificiais seriam os mais adequados para este grupo. As arcadas dentais completas foram moldadas com alginato e vazadas em gesso especial na parte oclusal e gesso pedra na base. Os dentes não apresentavam nenhum sinal de abrasões anormais, restaurações ou deformidades. A saúde periodontal era boa com mínima ou nenhuma retração gengival, inflamação ou hipertrofia. Os dentes dos modelos em gesso e os artificiais tiveram sua dimensão mesio-distal (largura) mensurada com um paquímetro digital. Não foi observada diferença significativa entre os sexos e entre as hemi-arcadas direita e esquerda com relação à largura dos dentes anteriores superiores. Das marcas analisadas nenhuma foi considerada apropriada para o grupo em questão devido ao fato de possuírem poucas opções de modelos e estes serem fabricados em tamanhos predominantemente pequenos enquanto que os dentes naturais mostraram-se predominantemente maiores (mais largos), o que nos apontou à necessidade de se adaptar ou criar modelos que sejam mais adequados à realidade brasileira. / It was studied the width of upper anterior teeth in 121 Brazilian college students intending to determine which models and brands would be more adequate to such group. The whole dental arch was molded with alginate and stone type four was poured in the oclusal surface of teeth while stone type two was poured in the left parts. Those teeth did not present abnormal abrasions, fillings or deformities. Periodont was healthy presenting little or none gengival retraction, inflamation or hipertrophy. Both stone models and artificial teeth had their mesio-distal distance (width) measured by a digital caliper rule. It was not observed significant difference between genders or right and left hemi-arches when comparing to the upper anterior teeths width. Considering the analyzed brands none was considered appropriate to such group because there were little options besides sizes being considered too small when compared to natural teeth, which pointed to the necessity to adapt or to create models more adequate to the Brazilian reality.
|
15 |
Redimensionamento de distribuidor pendular para grandes vazões de calcário / Pendulum spreader resizing for large limestone flow rateDuarte, Cássio da Costa 19 February 2019 (has links)
Aproximadamente 70% do solos com potencial agrícola no Brasil são classificados como solos ácidos, e para sua correção realiza-se, normalmente, a aplicação do calcário em pó. Apesar de ser o insumo sólido mais consumido no país, nota-se uma baixa qualidade em suas aplicações além da inexistência de equipamentos dedicados à sua aplicação e de esforços em pesquisa e desenvolvimento de novos conceitos de máquinas nesse sentido. Atualmente a maior parte das aplicações a lanço de granulados (fertilizantes) e pós (corretivos) são realizadas através de distribuídores centrífugos. Provavelmente essa tenha sido a razão para os fabricantes optaram por investir mais nessas máquinas, estagnando assim a evolução dos distribuidores de princípio pendular, os quais realizam as aplicações através do movimento oscilatório horizontal de um tubo. Diante desse cenário, buscou-se adaptar e redimensionar um distribuidor de princípo pendular dedicados à fertilizantes para aplicação de grandes vazões de calcário em pó. Fabricou-se um protótipo com mecanismo dosador volumétrico e acionamento do pêndulo via motor elétrico conectado a um inversor de frequência. Utilizou-se pêndulos de policloreto de vinila (PVC) com diferentes comprimentos com e sem rampa em suas extremidades. Os ensaios foram realizados em sete diferentes frequências, e mensurou-se a largura máxima de lançamento das partículas. Notou-se que tanto o incremento da frequência e do comprimento do pêndulo, assim como a utilização de uma rampa na extremidade foram, na maioria dos casos, capazes de produzir um aumento na distância de lançamento da partícula. Este estudo demonstrou a capacidade do protótipo em realizar aplicações de calcário em pó em faixa com uma vazão superior (até 6,5 kg s-1) às convencionais (1,5 kg s-1) com coeficientes de variação inferiores a 3,14 %. Além disso, mostou-se que é possivel variar a largura da faixa de aplicação de 1,89 m até 5,69 m com a mudança do comprimento do pêndulo, frequência e utilização da rampa. / Approximately 70% of the soils with agricutural potential in Brazil are classified as acid, and, for their neutralization the application of lime powder is usually carried out. Despite of being the most used solid agricultural input in the country, it can be noticed a low quality in its application, besides the lack of equipament dedicated exclusively to its application and of efforts in research and development of new concepts of machines in that sense. Currently, most of the granulated and powder application carried out through centrifugal spreaders. Probably this was the reason why manufactures opted to invest more in these kind of spreader, stagnating the evolution of pendulum spreaders, which realize the distribution through the horizontal oscillatory moviment of a tube (spout). In this context, it was intended to adapt and resize a pendular spreader dedicated to fertilizers for application of large flows of lime powder. A prototype with volumetric measure mechanism and eletric motor drive, connected to a frequency inverter, was developed. Polyvinyl chloride (PVC) pendulums with different lengths were used, with and without a ramp at their ends.. The tests were perfomed at seven different frequencies, and the higher widht distance was measured. It was noted that the increase in frequency and length of the tube, as well as the addition of a ramp at the border were, in most cases, able to increase the flight distance of the particles. This study demonstrated the ability of the prototype to spread limestone with a higher flow rate (up to 6.5 kg s-1) than the conventional ones (1.5 kg s-1) with coefficient of variation lower than 3.14%. Furthermore, it has been shown that is possible to vary the width of the application range form 1.89 m to 5.69 m by modifying the length of the tube, frequency and use of the ramp.
|
16 |
Técnicas de modulação para inversores fotovoltaicos sem transformador conectados à rede elétricaFARIAS, Alexandre Manoel de 31 January 2011 (has links)
Made available in DSpace on 2014-06-12T17:36:19Z (GMT). No. of bitstreams: 2
arquivo2570_1.pdf: 3284398 bytes, checksum: 3c6401d7832b0d8bdce327909ca35c12 (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2011 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Devido aos avanços tecnológicos, a sociedade vem consumindo mais energia, fazendo
com que os governantes tomem atitudes mais ativas no aumento do seu fornecimento.
Mundialmente, o carvão mineral é o combustível mais consumido para a geração de energia.
Porém, acordos entre alguns países estão fazendo com que essa energia tenha seu consumo
reduzido devido ao prejuízo e ao meio ambiente. Com isso as fontes renováveis de energia
vêm ganhando mais espaço na matriz energética. A fonte de energia mais consumida
no Brasil é a hidráulica e a participação da energia solar ainda é bastante reduzida e
limitada principalmente a eletrificação rural, onde não é viável a construção de linhas
de transmissão para a baixa potência instalada. A energia solar fotovoltaica, devido ao
seu avanço tecnológico, associado principalmente ao aumento do rendimento dos painéis
fotovoltaicos, vem conquistando um grande espaço nessa nova matriz, fazendo com que
alguns problemas de conexão à rede elétrica sejam resolvidos. O trabalho proposto visa
eliminar as correntes de dispersão dos painéis fotovoltaicos, que aparecem se não houver
isolação galvânica entre o sistema fotovoltaico e a rede elétrica. O controle é feito aplicando técnicas adequadas de modulação por largura de pulso, que são discutidas, simuladas e
verificadas experimentalmente. A conversão da energia solar fotovoltaica é feita com um
inversor multinível, garantindo que a tensão produzida nos painéis fotovoltaicos trabalhe
próxima ao ponto ótimo de operação, extraindo grande parte da máxima potência possível
dos painéis de acordo com as condições ambientais associadas
|
17 |
Estratégia de modulação escalar generalizada para conversores matriciaisBRADASCHIA, Fabrício 31 January 2008 (has links)
Made available in DSpace on 2014-06-12T17:37:34Z (GMT). No. of bitstreams: 2
arquivo5326_1.pdf: 6226336 bytes, checksum: b032c403949159cb4854d1cf615dceff (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Processadores de potência são dispositivos capazes de converter um conjunto de tensões,
com amplitude e freqüência fixas, em outro, com amplitude e freqüência controláveis.
O objetivo principal é controlar tais processadores para que funcionem como fontes de
alimentação ajustáveis para as cargas. Uma classe de processadores é a dos conversores
diretos de potência. Estes possuem vantagens significativas comparados aos conversores
indiretos tradicionais, como bidirecionalidade da potência, tensões na saída e correntes na
entrada senoidais, controle do fator de deslocamento na entrada e circuito compacto. Entre
as topologias de conversores diretos de potência, a topologia do conversor matricial é a
mais conhecida na literatura. Muitas técnicas para o controle das chaves dos conversores
matriciais foram propostas, mas não há uma estratégia simples que possa generalizar todas
essas técnicas de controle. Portanto, os objetivos dessa dissertação são: realizar um estudo
sobre a evolução dos conversores matriciais, apresentar o modelo matemático completo de
um conversor matricial trifásico, propor uma estratégia de modulação escalar generalizada
e comparar, através de simulações, três técnicas de controle conhecidas na literatura com as
três técnicas propostas a partir do estudo da estratégia de modulação generalizada
|
18 |
Avaliação do posicionamento de caninos superiores permanentes na fase da dentadura mista em relação à largura do arco dentário e ao espaço na região anterior / Evaluation of the maxillary canines position in mixed-dentition and width and anterior space relationshipSelma Sano Suga 19 March 2008 (has links)
Este estudo avaliou o posicionamento de caninos superiores permanentes em relação à largura do arco dentário superior e ao espaço na região anterior em pacientes na fase da dentadura mista. Foram analisados radiografias panorâmicas e modelos de estudo pré-tratamento de pacientes sem caninos deslocados (n = 68; 34 do gênero masculino; 34 do gênero feminino). A amostra foi dividida em idade e gênero. A largura do arco dentário e o espaço na região anterior entre os incisivos permanentes foram medidos. A posição e a inclinação do canino na radiografia panorâmica foram avaliadas em relação à linha mediana. Os resultados deste estudo mostram que não houve diferenças no posicionamento dos caninos permanentes em relação às variáveis analisadas. A média da angulação do canino superior em relação à linha mediana foi 6,2o e 10o para o gênero feminino e 9,2o e 11o para o masculino, respectivamente para o lado direito e esquerdo. / This study investigated the correlation between maxillary dental arch width, anterior space and the position of canines in patients during the mixed-dentition stage. Pretreatment Panoramic radiographs and dental casts were evaluated of randomly selected patients in the mixed dentition without maxillary canines displaced (n = 68; male, 34; female, 34). This sample was matched according to sex and age. Arch widths between the maxillary canines deciduous and anterior space between permanent incisors were measured and recorded. The position and inclination of canine on panoramic radiography was investigated. The results of this study showed that there are similarities in the position of the permanent canines in all cases and in both gender. The average of the canine\'s angulation to the mid-sagital plane was 6,2o and 10o for female and 9,2o and 11o for male, respectively to the right and left side.
|
19 |
Uso do sensoriamento remoto radiométrico para a estimativa da largura do rio na Bacia do Araguaia / The use of radiometric remote sensing for estimate river width in Araguaia BasinCruz, Patrícia Porta Nova da 30 July 2014 (has links)
Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-03-09T14:20:42Z
No. of bitstreams: 1
texto completo.pdf: 1608092 bytes, checksum: 92567b5aeb01fd37c556cf698ef08350 (MD5) / Made available in DSpace on 2016-03-09T14:20:42Z (GMT). No. of bitstreams: 1
texto completo.pdf: 1608092 bytes, checksum: 92567b5aeb01fd37c556cf698ef08350 (MD5)
Previous issue date: 2014-07-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Os recursos hídricos são de suma importância para a manutenção da vida em nosso planeta e, por isso, conhecer a sua real disponibilidade em uma localidade é uma questão primordial nos tempos atuais para estabelecer estratégias de uso racional e sustentável dos mesmos. Para isso, torna-se indispensável realizações de pesquisas que possibilitem obter informações sobre o comportamento e a dinâmica dos hidrossistemas continentais, o que pode ser feito por meio do uso combinado de dados climatológicos e hidrológicos concisos e representados por longas séries temporais. Porém, poucas regiões do globo dispõem de longos períodos com registros de dados para estudos rigorosos dos hidrossistemas continentais. E, ainda assim, mesmo nos locais onde existem longas séries de dados, poderá haver períodos com falhas ou informações inconsistentes, gerando limitações que penalizam e dificultam a compreensão da variabilidade de processos que regulam o funcionamento dos hidrossistemas continentais e a previsão do ciclo hidrológico. Para preencher a ausência de série de dados ou falhas nos mesmos, o sensoriamento remoto é uma ferramenta de grande potencial para se criar banco de dados com diversas aplicabilidades nas pesquisas hidrológicas, como por exemplo, a inicialização de modelos hidrológicos e para monitoramento hidrológico da região estudada. Assim, o objetivo deste trabalho é avaliar o uso de dados de sensoriamento remoto radiométrico a partir dos produtos MODIS para a estimativa da largura do rio na bacia do Araguaia através da detecção e estimativa da largura do rio Araguaia e de seus principais afluentes e gerando um banco de dados com mapas de largura dos rios para a bacia do Araguaia nos anos de 2000 a 2013. Notou-se que os dados MODIS são satisfatórios para detectar rios com larguras superiores a 232 m sendo que os dados analisados nessa faixa apresentaram erro relativo médio menor que 13% e de 28% para rios com largura entre 116 e 232 m. O MODIS é o sensor ideal para estimativa de largura do rio e monitoramento hidrológico para regiões onde não possui informações observadas. / Water resources are of great importance for the maintenance of life on our planet and, therefore, knowing their actual availability in a locality is a key issue in current times to establish strategies for rational and sustainable usage. For this, it is essential to conduct research that allows obtaining of information about the behavior and dynamics of continental hydrosystems, which can be done through the combined use of climatological and hydrological concise data and represented by long time series. However, few regions of the world have long periods with data records for rigorous studies of continental hydrosystems. And yet, even in places where there are long data series, there may be periods with fails or inconsistent information, generating limitations that penalize and difficult the understanding of processes variability that regulate the functioning of continental hydrosystems and the hydrological cycle prediction. To fill the absence of data series or gaps in them, remote sensing is a tool of great potential for creating database with various applications in hydrological research, such as the initialization of hydrologic models and hydrologic monitoring in the region studied. The objective of this study is to evaluate the use of remote sensing data from MODIS products for hydrological monitoring in the Araguaia River basin through the detection and estimation of the width of the Araguaia River and its main tributaries and generate a database with maps of wetlands and width of rivers for Araguaia basin for the years from 2000 to 2013. It was observed that MODIS data are satisfactory for detecting rivers with widths greater than 232 meters and the data analyzed in this range had average relative error less than 15% and 28% for rivers with a width between 116 and 232 meters. The MODIS is ideal sensor for estimating the width of the river and hydrological monitoring for regions where no information has observed.
|
20 |
Decomposição e largura em árvore de grafos planares livres de ciclos pares induzidos / Decomposition and width in tree of graphs to glide free of cycles induced pairsSilva, Aline Alves da January 2007 (has links)
SILVA, Aline Alves da. Decomposição e largura em árvore de grafos planares livres de ciclos pares induzidos. 2007. 71 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T19:42:38Z
No. of bitstreams: 1
2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T19:43:21Z (GMT) No. of bitstreams: 1
2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Made available in DSpace on 2016-05-20T19:43:21Z (GMT). No. of bitstreams: 1
2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5)
Previous issue date: 2007 / The definitions of tree decomposition and treewidth were introduced by Robertson and Seymour in their series of papers on graph minors, published during the nineties. It is known that many NP-hard problems can be polynomially solved if a tree decomposition of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes of graphs. In this context, the planar graphs seem to be specially challenging because, in despite of having many known bounded metrics (for example, chromatic number), they have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass of planar graphs. In this work, we investigate the class of even-hole-free planar graphs. We show that if G is an even-hole-free planar graph, then it does not contain a subdivision of the 10£10 grid. So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most 49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition of a even-hole-free planar graph are given, both based on known characterizations of even-hole-free graphs. In the ¯rst one, a tree decomposition is built from basic graphs by concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1; 2; 3) and 2-join cutsets. In the second one, a tree decomposition is built by including one by one the vertices of G, following their bi-simplicial order. / Os conceitos de Decomposição em Árvore e Largura em Árvore foram introduzidos por Robertson e Seymour em sua série de artigos sobre menores de grafos, publicados ao longo da década de 90. Sabe-se que muitos problemas NP - difíceis podem ser resolvidos polinomialmente para um grafo G, dada uma decomposição em Árvore de G de largura limitada. Logo, limitar a largura em árvore de uma classe de grafos torna-se um objeto de estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante intrigante, uma vez que, apesar de possuir outras métricas limitadas em valores baixos (por exemplo, número cromático), não possui largura em árvore limitada. Desta forma, uma alternativa é restringir a classe estudada para uma subclasse dos grafos planares. Neste trabalho, nós investigamos a classe dos grafos planares livres de buracos pares. Nós mostramos que se G é um grafo planar livre de buracos pares, então ele não contém uma subdivisão de uma grade 10 £ 10. Portanto, se os menores grades de G são obtidos de subdivisões G tem largura em árvore no máximo 49. Além disso, dois algoritmos não exatos polinomiais para computar uma decomposição em árvore de um grafo planar livre de buracos pares são apresentados, ambos baseados em caracterizações conhecidas de tal classe de grafos. No primeiro algoritmo, uma decomposição em árvore é construída a partir de grafos básicos pela concatenação de decomposições em árvores de pedaços pequenos via os cortes clique, k-estrelas (k = 1; 2; 3) e 2-join. No segundo, uma decomposição em árvore é construída pela inclusão dos vértices de G um a um, seguindo sua ordem bi-simplicial.
|
Page generated in 0.0341 seconds