Atilio G. Luiz, C. N. Campos, and R. Bruce Richter.

Abstract:A graceful labelling of a tree is an injective function such that . An -labelling of a tree is a graceful labelling with the additional property that there exists an integer such that, for each edge , either or . In this work, we prove that the following families of trees with maximum degree three have -labellings: lobsters with maximum degree three, without -legs and with at most one forbidden ending; trees with a perfect matching such that the contraction has a balanced bipartition and an -labelling; and trees with a perfect matching such that their contree is a caterpillar with a balanced bipartition. These results reinforce the conjecture that every tree with maximum degree three and a perfect matching has an -labelling.

Atilio G. Luiz, C. N. Campos, and R. Bruce Richter.

Abstract:A graceful labelling of a tree is an injective function such that . A tree is said to be 0-rotatable if, for each , there exists a graceful labelling of such that . In this work, it is proved that if is a caterpillar with and, for every non-leaf vertex , the number of leaves adjacent to is at least , then is -rotatable. This result reinforces the conjecture that every caterpillar with diameter at least five is 0-rotatable.

Atilio G. Luiz, C. N. Campos, and R. Bruce Richter.

Abstract:A graceful labelling of a tree is an injective function such that . A tree is said to be 0-rotatable if, for any , there exists a graceful labelling of such that . In this work, it is proved that the following families of caterpillars are 0-rotatable: caterpillars with a perfect matching; caterpillars obtained by identifying a central vertex of a path with a vertex of ; caterpillars obtained by linking one leaf of the star to a leaf of a path with and ; and caterpillars with diameter five or six. These results reinforce the conjecture that all caterpillars with diameter at least five are 0-rotatable.

Joao Meidanis - Priscila Biller - Joao Paulo Pereira Zanetti.

Resumo:Começamos a reestruturar estas notas em 2016, quando Meidanis esteve em licença sabática na Universidade de Ottawa, no laboratório de David Sankoff. Usamos o termo ``reestruturar'' porque os principais resultados exibidos aqui, sobre genomas minimax sob a distância de posto, apareceram primeiro no texto apresentado por Biller em seu exame de qualificação para o doutorado, escrito em 2014. O conteúdo é dividido em seis capítulos, como segue. No Capítulo 1 introduzimos as primeiras definições, incluindo matrizes genômicas, distância, e órbitas. Também derivamos uma importante fórmula para a distância com base em órbitas. No Capítulo 2 definimos operações em genomas, com foco naquelas de posto pequeno. O capítulo se encerra com a definição de operações básicas, a saber, cortes, junções, e duplas trocas. No Capítulo 3 estudamos cenários de ordenação indo de um genoma para outro através de operações básicas. Mostramos que a partir de cada genoma podemos alcançar qualquer outro com tais cenários. Isto fornece ademais uma forma alternativa de calcular a distância. Genomas intermediários são o tópico do Capítulo 4. Eles podem ser caracterizados como membros de cenários ótimos, ou como genomas para os quais se verifica igualdade na desigualdade triangular. Eles são também as medianas de dois genomas. Uma noção relacionada é a noção de genomas minimax, explorada no Capítulo 5. Estabelecemos um limite inferior para a pontuação minimax, e mostramos exatamente os casos onde é possível atingir este limite. Em qualquer caso, é sempre possível encontrar um genoma a menos de uma unidade do limite inferior. Finalmente, o Capítulo 6 lida com uma interessante propriedade de paridade da distância de posto.

Abstract:We started the work of reshaping these notes in 2016, when Meidanis was on sabbatical at the University of Ottawa, in David Sankoff's lab. We use the term ``reshaping'' because the main results shown here, on minimax genomes under the rank distance, were first presented in Biller's text for her PhD qualifying exam, written in 2014. The contents are divided in six chapters, as follows. In Chapter 1 we introduce the first definitions, including genome matrices, distance, and orbits. We also derive an important formula for the distance based on orbits. In Chapter 2 we define operations on genomes, with focus on those with small rank. The chapter closes with the definition of basic operations, namely, cuts, joins, and double swaps. In Chapter 3 we study sorting scenarios going from a genome to another by basic operations. We show that from every genome we can reach any other with such scenarios. This also provides an alternative way of computing the distance. Intermediate genomes are the topic of Chapter 4. They can be characterized both as optimal scenario members, and as genomes for which the triangle inequality becomes an equality. They are also the medians of two genomes. A related notion is that of a minimax genome, explored in Chapter 5. We establish a lower bound for the minimax score, and show exactly the cases where it is possible to achieve such a score. In any case, it is always possible to find a genome within 1 unit of the lower bound. Finally, Chapter 6 deals with an interesting parity property of the rank distance.

Adilson Luiz Bonifacio and Arnaldo Vieira Moura.

Abstract:Model based testing is a well-established approach to test reactive systems described by formal models. In this paper we look at the problem of generating complete test suite for reactive systems formally described as Input Output Labeled Transition Systems (IOLTSs). In this work we propose a new notion of conformance relation for IOLTS models based on formal languages and automata. We show that this new conformance relation is more general than the well-studiediococonformance relation. We then describe how to generate test suites that are sound and exhaustive for a given specification model, according to the new conformance relation. We impose no restrictions on the structure of the specification model, a distinct advantage when compared to other recent works.

Pedro M. Moura and Nelson L. S. da Fonseca.

Resumo:This technical report proposes a Routing, Core and Spectrum Assignment (RCSA) algorithm based on image processing Inscribed rectangle algorithm. The solution aims at discovering portions of spectrum capable of accommodating requests with low computational complexity. Advanced fitting policies are proposed to chose which portion of the spectrum to reduce of blocking and crosstalk. Results show that the proposed algorithm can reduce the blocking ratio under low loads and crosstalk under all loads, when compared to other RCSA algorithms in the literature.

Pedro M. Moura and Nelson L. S. da Fonseca.

Resumo:This technical report introduces a novel Routing, Core and Spectrum Assignment (RCSA) algorithm based on the Connected Component Labelling (CCL) algorithm. The RCSA algorithm represents the spectrum of multicore fibers as matrices and the CCL algorithm discovers with low computational complexity the available spectrum to allocate to a connection request. Spectrum fitting policies are also proposed to be jointly employed with the CCL algorithm. Results show the feasibility of utilizing image processing algorithms such as the CCL in RCSA algorithms, given that they demand low computational complexity and yet produce low blocking ratio.

Pedro M. Moura, Rafael A. Scaraficci, and Nelson L. S. da Fonseca.

Resumo:Information and Communication Technology activities consumed 4% of the world energy in 2009, and such consumption will continue to increase due to the traffic growth of the Internet predicted for the next years. Techniques to make the core of the network more energy efficient has been proposed, among them, green routing has been considered a promising technique. This technical report proposes a novel Routing, Modulation Level and Spectrum Assignment (RMLSA) algorithm for elastic optical networks that considers the energy consumption of potential routes. Results indicate that this algorithm can save up to 34% energy and produce bandwidth blocking ratio two orders of magnitude lower than existing energy aware RMLSA algorithms.

Pedro M. Moura, Rafael A. Scaraficci, and Nelson L. S. da Fonseca.

Resumo:This technical report introduces a novel traffic grooming algorithm for the connection establishment of deadline-driven requests in elastic optical networks, named Elastic Batch Grooming Algorithm. The algorithm grooms batches of requests to establish lightpaths with diverse bandwidth demands with deadline requirements. Results show that the algorithm significantly reduces the blocking ratio and the number of demanded transponder when compared to traditional non-batch algorithms.

Jane Dirce Alves Sandim Eleuterio and Cecilia Mary Fisher Rubira.

Abstract:Modern systems need to able to self-adapt to changing user needs and system environments. Examples of systems that demand self-adaptive capabilities include mobile devices applications that should deal with environmental changes and service-oriented systems that should replace unreliable services on-the-fly. In this context, dynamic software product line (DSPL) is an engineering approach for developing adaptive systems based on commonalities and variabilities for a family of similar systems. However, researchers have reported that many DSPL solutions fail to meet all the system’s adaptability requirements, and in many cases, they are developed in ad hoc manner. This paper surveys various DSPL solutions, evaluates and compares their different design strategies. A two-dimension taxonomy is specified to address basic technical issues for a given DSPL proposal. The DSPL dimension classifies the different design choices for implementing variability schemes, and for creating different kinds of feature models. The Self-adaptation dimension classifies the different design choices for the adaptation requirements and for the MAPE-K control loop implementation. Practical issues and difficulties are summarized, major trends in actual DSPL proposals are identified, and directions for future work are suggested.

Helder M. N. S. Oliveira and Nelson L. S. da Fonseca.

Abstract:In optical networks, failures can imply in great loss of data due to high transmission rates, leading to the need of employment of protection mechanisms. This paper introduces a novel algorithm to provide Failure-independent path protecting p-cycle with minimum interference for path protection in elastic optical networks using space division multiplexing. The proposed protection algorithm reduces rejections of future requests and make no assumption about specific patterns of arrival of requests. The algorithm is compared to FIPPMC algorithm and a algorithm based on methods of []. Results indicate that the 100% protection for single failures can be provided by the proposed algorithm.

Helder M. N. S. Oliveira and Nelson L. S. da Fonseca.

Abstract:In recent years, elastic optical networks have emerged as a solution for dealing with the diversity of the bandwidth demands of network applications. The use of only two multiplexing dimensions has limited the network capacity. To ameliorate this problem, a third dimension has been added in space-division multiplexing (SDM). As transmission rates increase so does the need for protection against network failures. Among the protection schemes, those protecting paths are of great interest due to their end-to- end solutions. This paper introduces a novel algorithm based on p-cycle to provide failure-independent path protection in elastic optical networks with SDM.

Daniel Cason and Luiz Eduardo Buzato.

Abstract:Informally, total order broadcast protocols allow processes to send messages with the guarantee that all processes eventually deliver the messages in the same order. In this paper, we investigate the efficiency and performance of On-Time Fast Paxos a synchronous total order broadcast protocol for the crash-recover failure model that is built atop a broadcast-based asynchronous distributed system. On-Time Fast Paxos combines an asynchronous consensus protocol, Fast Paxos, with a synchronous communication protocol while guaranteeing the original safety and liveness properties of Fast Paxos. The synchronous communication protocol relies on virtual global time to create the synchronicity necessary to make Fast Paxos work at its theoretical optimum, two communication steps. Experimental results allow us to conclude that On-Time Fast Paxos performs very well both in terms of throughput and latency, reaches 960mbps in a 1Gbps network with an average latency of 2ms. Finally, its novel hybrid design, asynchronous layer driven by a synchronous layer, shows that, time and synchrony be used to improve the performance of total order broadcast protocols.

Gilcélia Regiâne de Souza and Jorge Stolfi.

Resumo:Aplicamos o algoritmo geral top-down para a aproximação adaptativa em multinível HApp, descrito na Parte I deste artigo, para um tipo específico de bases de função de aproximação que chamamos de bases regulares em multinível. O algoritmo garante um erro máximo de aproximação especificado em cada ponto de amostragem. Embora a base adaptativa resultante não seja necessariamente mínima, esta pode ser muito menor do que a base completa, para as funções a ser aproximadas com detalhes locais em várias escalas de resolução espacial. Os elementos da base são splines tensoriais com suporte compacto. Estas bases são semelhantes à bases wavelet padrão, exceto que elas fornecem fórmulas analíticas para a função de aproximação; que podem ser utilizados, por exemplo, para diferenciação e interpolação entre os pontos de amostragem. Nesta parte do artigo, assumimos uma grade regular de Pontos de amostragem e um domínio tipo caixa com topológia toroidal. Estas escolhas permitem economias consideráveis de tempo de computação. Também utilizamos em cada nível um operador modificados de mínimo quadrados com rejeição Bayesiana de outlier.

Instituto de Computação ::
Universidade Estadual de Campinas
Av. Albert Einstein, 1251 - Cidade Universitária Zeferino Vaz • 13083-852 Campinas, SP - Brasil • Fone: [19] 3521-5838 |