Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.

Implicit optimality criterion for convex SIP problem with box constrained index set

We consider a convex problem of Semi-Infinite Programming (SIP) with multidimensional index set. In study of this problem we apply the approach suggested in [20] for convex SIP problems with one-dimensional index sets and based on the notions of immobile indices and their immobility orders. For the problem under consideration we formulate optimality conditions that are explicit and have the form of criterion. We compare this criterion with other known optimality conditions for SIP and show its efficiency in the convex case.

Micropropagation in elite corck oak trees: a tool for suber production improvement?

Dada a extrema importância económica e ambiental que o montado de sobro tem em Portugal, e dado o declínio deste devido a várias razões (e.g. doença, idade das plantas) é premente desenvolver estratégias de preservação de sobreiros elite e optimizar técnicas para a propagação destes genótipos. No primeiro Capítulo expõe-se uma breve introdução sobre o montado actual e as técnicas actuais de regeneração/propagação do sobreiro. Descreve-se ainda as principais técnicas de preservação e avaliação de estabilidade genética referidas na literatura para sobreiro e outras lenhosas. No Capítulo II é apresentado um estudo de melhoramento das condições actuais de maturação de embriões somáticos de sobreiro com vista a aperfeiçoar o processo de conversão em plantas. Neste capítulo é apresentado um protocolo melhorado em relação ao actual que permite um desenvolvimento dos embriões somáticos dum modo semelhante aos embriões zigóticos em termos de substâncias de reserva. O Capítulo III mostra um estudo efectuado com o objectivo principal de avaliar estabilidade genética durante todo o processo de embriogénese somática. Neste capítulo são apresentados resultados duma análise feita por RAPD em fases distintas da embriogénese somática de sobreiro. Neste estudo mostra-se que não existem diferenças significativas entre plantas de campo, embriões somáticos e plantas regeneradas. No Capítulo VI, pretende-se complementar o estudo anterior. Neste Capítulo descreve-se a dinâmica do ciclo celular durante as primeiras fases de embriogénese somática na presença de reguladores de crescimento. Este trabalho permitiu concluir a importância dos reguladores de crescimento na indução e perceber o peso do factor genótipo durante o processo. Considerando os resultados anteriores, a necessidade de um processo eficiente de preservação de genótipos elite torna-se fundamental. No Capítulo V descreve-se um protocolo de criopreservação eficiente sem recursos a substâncias tóxicas. Nesta secção é ainda feita uma análise de variabilidade genética após criopreservação através de FCM, AFLP e SSR. Todos os resultados obtidos anteriormente são postos a prova no Capítulo VI onde se faz uma monitorização extensiva de 10 genótipos elite, tendo em conta a sua capacidade de produção de cortiça, através do processo de embriogénese somática. Durante esta secção são utilizados os protocolos desenvolvidos anteriormente e avaliados na sua eficiência. Neste capítulo é descrita a integração de vários segmentos deste estudo num só protocolo eficiente de regeneração e preservação de sobreiros através de embriogénese somática. Finalmente, no Capítulo VI são apresentadas as conclusões da presente Tese de Doutoramento, com especial incidência para linhas de investigação futuras a serem tomadas. Discute-se a importância deste novo protocolo na optimização da produção da cortiça e traçam-se possíveis aplicações alternativas.