Upper palaeozoic stratigraphy and palynology of OMZ, NW and SW Portugal

Neste trabalho descreve-se e interpreta-se a estratigrafia e palinologia de rochas sedimentares e metassedimentos de idade devónica e carbónica aflorantes ao longo da zona de cisalhamento Porto-Tomar, a Sul na Bacia de Santa Susana e em vários locais onde afloram os Calcários de Odivelas. Existe um registo de sedimentação descontínuo possivelmente associado a esta zona de cisalhamento desde o Devónico Superior até ao Pennsylvaniano. Desde o Devónico Superior até ao Mississippiano esta sedimentação é marinha, de carácter essencialmente turbiditico com uma tendência geral para se tornar mais proximal. A maturação térmica atingida por estas rochas (Unidade de Albergaria-a-Velha) é alta e a unidade é considerada pós-madura em termos de potencial gerador de hidrocarbonetos. O metamorfismo incipiente é acompanhado por intensa deformação. A bacia do Buçaco é inteiramente terrestre e tem a sua idade restrita ao Gjeliano (Pennsylvaniano superior). O controlo da sedimentação pela actividade da zona de cisalhamento Porto-Tomar é evidente. A sua maturação térmica é relativamente baixa (dentro da catagénese) e a deformação menos intensa, contrastando com a Unidade de Albergaria-a-Velha com a qual parece ter uma relação geométrica complexa, de origem tectónica. As relações de campo e dados da maturação térmica permitem inferir um evento térmico e de deformação à escala regional entre o Serpukoviano e o Gjeliano e outro, essencialmente de deformação, entre o Gjeliano e o Carniano (Triássico Superior). A bacia de Santa Susana tem características semelhantes à do Buçaco, visto estar enquadrada também numa zona de cisalhamento importante que neste caso separa a Zona de Ossa-Morena da Zona Sul Portuguesa. A sua idade é kasimoviana, possivelmente também moscoviana (Pennsylvaniano médio). A evolução térmica da bacia e a relação estrutural com as unidades circundantes permite inferir um evento térmico e de deformação regionalmente importante entre o Viseano e o (?)Moscoviano-Kasimoviano. O estudo detalhado de vários locais onde afloram os Calcários de Odivelas permite desenhar uma paleogeografia regional durante o intervalo Emsiano terminal-Givetiano (fim do Devónico Inferior – Devónico Médio) para o sector Oeste da Zona de Ossa-Morena: Actividade vulcânica em regime marinho (e talvez subaéreo), formando edifícios vulcânicos no topo dos quais (e possivelmente também em altos fundos estruturais) se instalaram recifes, tendo a comunidade recifal, em termos de diversidade, persistido durante todo ou grande parte deste intervalo de tempo. O evento Choteč basal é observável num destes locais.

A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.