Majorantes para a ordem de subgrafos induzidos k-regulares

Muitos dos problemas de otimização em grafos reduzem-se à determinação de um subconjunto de vértices de cardinalidade máxima que induza um subgrafo k-regular. Uma vez que a determinação da ordem de um subgrafo induzido k-regular de maior ordem é, em geral, um problema NP-difícil, são deduzidos novos majorantes, a determinar em tempo polinomial, que em muitos casos constituam boas aproximações das respetivas soluções ótimas. Introduzem-se majorantes espetrais usando uma abordagem baseada em técnicas de programação convexa e estabelecem-se condições necessárias e suficientes para que sejam atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro das matrizes de adjacência, laplaciana e laplaciana sem sinal. É ainda apresentado um algoritmo não polinomial para a determinação de umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular de ordem máxima para uma classe particular de grafos. Finalmente, faz-se um estudo computacional comparativo com vários majorantes e apresentam-se algumas conclusões.

Cross-readings and ecoliteracy in children's pop-up books

The purpose of this text is to analyse two recently been published pop-up books aimed at children, by Anouck Boisrobert e Louis Rigaud, Popville (2009) and Dans la forêt du paresseux [Wake up, Sloth!, En el bosque del perezoso] (first published in 2009 and 2012, accompanied with texts by Joy Sorman and Sophie Strady, respectively). These books were published originally in France by Hélium Editions, but they can now be found in several western countries and in many languages (Catalan, French, Dutch, English, German, Italian, Portuguese and Spanish, at least). The objective is to analyse their verbal text and their visual aspects produced by a sophisticated paper engineered to question how they achieve what seems to be one of their goals, the promotion of the readers' ecoliteracy (Orr, 1992) by his involvement in the reading process. This issue seems to be one of the main trends on children's literature in western societies nowadays, transcending the traditional and almost omnipresent role of scenario that nature plays in many children's narratives.