Technical Reports Published in 2017

  • IC-17-14 pdf bib
    On $\alpha$-labellings of lobsters and trees with a perfect matching.
    Atilio G. Luiz, C. N. Campos, and R. Bruce Richter.
    August 2017. In English, 15 pages.

    Abstract: A graceful labelling of a tree $T$ is an injective function $f 
         \colon        V(T)       \to       \{0,\ldots,\vert      
         E(T)\vert\}$ such that $\{\vert f(u)-f(v)\vert \colon
         uv      \in      E(T)\}      =     \{1,\ldots,\vert    
         E(T)\vert\}$. An $\alpha$-labelling of a tree $T$ is a graceful labelling $f$ with the additional property that there exists an integer $k 
         \in   \{0,\ldots,\vert  E(T)\vert\}$ such that, for each edge $uv \in E(T)$, either $f(u)
         \leq  k < f(v)$ or $f(v)     \leq    k    <   
         f(u)$. In this work, we prove that the following families of trees with maximum degree three have $\alpha$-labellings: lobsters with maximum degree three, without $Y$-legs and with at most one forbidden ending; trees $T$ with a perfect matching $M$ such that the contraction $T/M$ has a balanced bipartition and an $\alpha$-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 $\alpha$-labelling.

  • IC-17-13 pdf bib
    On 0-rotatable caterpillars with diameter at least 7.
    Atilio G. Luiz, C. N. Campos, and R. Bruce Richter.
    August 2017. In English, 05 pages.

    Abstract: A graceful labelling of a tree $T$ is an injective function $f 
         \colon        V(T)       \to       \{0,\ldots,\vert      
         E(T)\vert\}$ such that $\{\vert f(u)-f(v)\vert \colon
         uv      \in      E(T)\}      =     \{1,\ldots,\vert    
         E(T)\vert\}$. A tree $T$ is said to be 0-rotatable if, for each $v 
         \in   V(T)$, there exists a graceful labelling $f$ of $T$ such that $f(v)  =  0$. In this work, it is proved that if $T$ is a caterpillar with $diam(T)\geq   7$ and, for every non-leaf vertex $v  \in  V(T)$, the number of leaves adjacent to $v$ is at least $2+2((diam(T)-1)\bmod{2})$, then $T$ is $0$-rotatable. This result reinforces the conjecture that every caterpillar with diameter at least five is 0-rotatable.

  • IC-17-12 pdf bib
    Some families of 0-rotatable graceful caterpillars.
    Atilio G. Luiz, C. N. Campos, and R. Bruce Richter.
    August 2017. In English, 17 pages.

    Abstract: A graceful labelling of a tree $T$ is an injective function $f 
         \colon       V(T)       \to      \{0,1,\ldots,\vert     
         E(T)\vert\}$ such that $\{\vert f(u)-f(v)\vert \colon
         uv      \in     E(T)\}     =     \{1,2,\ldots,\vert    
         E(T)\vert\}$. A tree $T$ is said to be 0-rotatable if, for any $v 
         \in   V(T)$, there exists a graceful labelling $f$ of $T$ such that $f(v)  =  0$. 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 $P_n$ with a vertex of $K_2$; caterpillars obtained by linking one leaf of the star $K_{1,s-1}$ to a leaf of a path $P_n$ with $n  \geq 3$ and $s
         \geq   \lceil   \frac{n}{2}  \rceil$; and caterpillars with diameter five or six. These results reinforce the conjecture that all caterpillars with diameter at least five are 0-rotatable.

  • IC-17-11 pdf bib
    A Matrix-Based Theory for Genome Rearrangements.
    Joao Meidanis - Priscila Biller  - Joao Paulo Pereira Zanetti.
    August 2017. In English, 45 pages.

    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.

  • IC-17-10 pdf bib
    Generating complete test suites for reactive systems.
    Adilson Luiz Bonifacio and Arnaldo Vieira Moura.
    July 2017. In English, 25 pages.

    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-studied ioco conformance 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.

  • IC-17-09 pdf bib
    Inscribed rectangles algorithm for routing, core and spectrum assignment for sdm optical networks.
    Pedro M. Moura and Nelson L. S. da Fonseca.
    June 2017. In English, 13 pages.

    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.

  • IC-17-08 pdf bib
    Routing, core and spectrum assignment based on connected component labelling for sdm optical networks.
    Pedro M. Moura and Nelson L. S. da Fonseca.
    June 2017. In English, 13 pages.

    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.

  • IC-17-07 pdf bib
    Algorithm for energy efficient routing, modulation and spectrum assignment.
    Pedro M. Moura, Rafael A. Scaraficci, and Nelson L. S. da Fonseca.
    June 2017. In English, 13 pages.

    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.

  • IC-17-06 pdf bib
    Traffic grooming of batches of deadline-driven requests in elastic optical networks.
    Pedro M. Moura, Rafael A. Scaraficci, and Nelson L. S. da Fonseca.
    June 2017. In English, 13 pages.

    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.

  • IC-17-05 pdf bib
    A Comparative Study of Dynamic Software Product Line Solutions for Building Self-Adaptive Systems.
    Jane Dirce Alves Sandim Eleuterio and Cecilia Mary Fisher Rubira.
    April 2017. In English, 36 pages.

    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.

  • IC-17-04 pdf bib
    The Minimum Interference p-Cycle Algorithm for Protection of Space Division Multiplexing Elastic Optical Networks.
    Helder M. N. S. Oliveira and Nelson L. S. da Fonseca.
    April 2017. In English, 13 pages.

    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.

  • IC-17-03 pdf bib
    Algorithm for Protection of Space Division Multiplexing Elastic Optical Networks.
    Helder M. N. S. Oliveira and Nelson L. S. da Fonseca.
    April 2017. In English, 12 pages.

    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.

  • IC-17-02 pdf bib
    On-time fast paxos.
    Daniel Cason and Luiz Eduardo Buzato.
    February 2017. In English, 30 pages.

    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.

  • IC-17-01 pdf bib
    Adaptive multiscale function approximation - II: General discrete bases.
    Gilcélia Regiâne de Souza and Jorge Stolfi.
    January 2017. In English, 24 pages.

    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