On the Hamilton-Waterloo problem

The Hamilton-Waterloo problem asks for a 2-factorisation of K-v in which r of the 2-factors consist of cycles of lengths a(1), a(2),..., a(1) and the remaining s 2-factors consist of cycles of lengths b(1), b(2),..., b(u) (where necessarily Sigma(i)(=1)(t) a(i) = Sigma(j)(=1)(u) b(j) = v). In thus paper we consider the Hamilton-Waterloo problem in the case a(i) = m, 1 less than or equal to i less than or equal to t and b(j) = n, 1 less than or equal to j less than or equal to u. We obtain some general constructions, and apply these to obtain results for (m, n) is an element of {(4, 6)1(4, 8), (4, 16), (8, 16), (3, 5), (3, 15), (5, 15)}.

Trade spectra of complete partite graphs

The trade spectrum of a graph G is essentially the set of all integers t for which there is a graph H whose edges can be partitioned into t copies of G in two entirely different ways. In this paper we determine the trade spectrum of complete partite graphs, in all but a few cases.

Factorizations of and by powers of complete graphs

Let K-k(d) denote the Cartesian product of d copies of the complete graph K-k. We prove necessary and sufficient conditions for the existence of a K-k(r)-factorization of K-pn(s), where p is prime and k > 1, n, r and s are positive integers. (C) 2002 Elsevier Science B.V. All rights reserved.

Further decompositions of complete tripartite graphs into 5-cycles

Let K(r,s,t) denote the complete tripartite graph with partite sets of sizes r, s and t, where r less than or equal to s less than or equal to t. Necessary and sufficient conditions are given for decomposability of K(r, s, t) into 5-cycles whenever r, s and t are all even. This extends work done by Mahmoodian and Mirza-khani (Decomposition of complete tripartite graphs into 5-cycles, in: Combinatorics Advances, Kluwer Academic Publishers, Netherlands, 1995, pp. 235-241) and Cavenagh and Billington. (C) 2002 Elsevier Science B.V. All rights reserved.

Strongly regular graphs from differences of quadrics

In this note strongly regular graphs with new parameters are constructed using nested "blown up" quadrics in projective spaces. (C) 2002 Elsevier Science B.V. All rights reserved.

On the volume of 4-cycle trades

A 4-cycle trade of volume t corresponds to a simple graph G without isolated vertices, where the edge set can be partitioned into t 4-cycles in at least two different ways such that the two collections of 4-cycles have no 4-cycles in common. The foundation of the trade is v = \V(G)\. This paper determines for which values oft and a there exists a 4-cycle trade of volume t and foundation v.

Predicting cave initiation and propagation

The most widely used method for predicting the onset of continuous caving is Laubscher's caving chart. A detailed examination of this method was undertaken which concluded that it had limitations which may impact on results, particularly when dealing with stronger rock masses that are outside current experience. These limitations relate to inadequate guidelines for adjustment factors to rock mass rating (RMR), concerns about the position on the chart of critical case history data, undocumented changes to the method and an inadequate number of data points to be confident of stability boundaries. A review was undertaken on the application and reliability of a numerical method of assessing cavability. The review highlighted a number of issues, which at this stage, make numerical continuum methods problematic for predicting cavability. This is in particular reference to sensitivity to input parameters that are difficult to determine accurately and mesh dependency. An extended version of the Mathews method for open stope design was developed as an alternative method of predicting the onset of continuous caving. A number of caving case histories were collected and analyzed and a caving boundary delineated statistically on the Mathews stability graph. The definition of the caving boundary was aided by the existence of a large and wide-ranging stability database from non-caving mines. A caving rate model was extrapolated from the extended Mathews stability graph but could only be partially validated due to a lack of reliable data.

The tree cut and merge algorithm for estimation of network reliability

This article presents Monte Carlo techniques for estimating network reliability. For highly reliable networks, techniques based on graph evolution models provide very good performance. However, they are known to have significant simulation cost. An existing hybrid scheme (based on partitioning the time space) is available to speed up the simulations; however, there are difficulties with optimizing the important parameter associated with this scheme. To overcome these difficulties, a new hybrid scheme (based on partitioning the edge set) is proposed in this article. The proposed scheme shows orders of magnitude improvement of performance over the existing techniques in certain classes of network. It also provides reliability bounds with little overhead.

Decompositions of complete graphs into theta graphs with fewer than ten edges

A theta graph is a graph consisting of three pairwise internally disjoint paths with common end points. Methods for decomposing the complete graph K-nu into theta graphs with fewer than ten edges are given.

Mapping the royal road and other hierarchical functions

In this paper we present a technique for visualising hierarchical and symmetric, multimodal fitness functions that have been investigated in the evolutionary computation literature. The focus of this technique is on landscapes in moderate-dimensional, binary spaces (i.e., fitness functions defined over {0, 1}(n), for n less than or equal to 16). The visualisation approach involves an unfolding of the hyperspace into a two-dimensional graph, whose layout represents the topology of the space using a recursive relationship, and whose shading defines the shape of the cost surface defined on the space. Using this technique we present case-study explorations of three fitness functions: royal road, hierarchical-if-and-only-if (H-IFF), and hierarchically decomposable functions (HDF). The visualisation approach provides an insight into the properties of these functions, particularly with respect to the size and shape of the basins of attraction around each of the local optima.

Influência do substrato e do enraizamento na aclimatização de Melocactus glaucescens Buining & Brederoo propagados in vitro

Melocactus glaucescens (Cactaceae) é espécie endêmica da Bahia e está incluída na lista da IUCN e MMA como ameaçada de extinção. A transferência da condição in vitro para o ambiente ex vitro é uma etapa crítica, podendo ser um fator limitante para a produção das mudas micropropagadas. O objetivo deste trabalho foi analisar o efeito de diferentes substratos e do enraizamento na aclimatização de Melocactus glaucescens. As plantas propagadas in vitro foram mantidas sob 100% de luminosidade, com regas diárias por 75 dias. Os resultados demonstraram que o substrato adequado para a aclimatização deve conter 50% de terra vegetal e 50% de areia lavada; o tamanho mínimo do diâmetro e do comprimento da parte aérea para transferência para as condições ex vitro é de 5 mm e que as etapas de enraizamento in vitro e rustificação podem ser eliminadas da micropropagação de M. glaucescens. Estudos para demonstrar tempos de dessecação dos brotos acima de 5 mm são necessários, para se eliminar completamente a etapa do enraizamento in vitro para esta espécie.

GUI Inspection from Source Code Analysis

Graphical user interfaces (GUIs) are critical components of todays software. Given their increased relevance, correctness and usability of GUIs are becoming essential. This paper describes the latest results in the development of our tool to reverse engineer the GUI layer of interactive computing systems. We use static analysis techniques to generate models of the user interface behaviour from source code. Models help in graphical user interface inspection by allowing designers to concentrate on its more important aspects. One particularly type of model that the tool is able to generate is state machines. The paper shows how graph theory can be useful when applied to these models. A number of metrics and algorithms are used in the analysis of aspects of the user interface's quality. The ultimate goal of the tool is to enable analysis of interactive system through GUIs source code inspection.

Program slicing by calculation

Program slicing is a well known family of techniques used to identify code fragments which depend on or are depended upon specific program entities. They are particularly useful in the areas of reverse engineering, program understanding, testing and software maintenance. Most slicing methods, usually oriented towards the imperative or object paradigms, are based on some sort of graph structure representing program dependencies. Slicing techniques amount, therefore, to (sophisticated) graph transversal algorithms. This paper proposes a completely different approach to the slicing problem for functional programs. Instead of extracting program information to build an underlying dependencies’ structure, we resort to standard program calculation strategies, based on the so-called Bird-Meertens formalism. The slicing criterion is specified either as a projection or a hiding function which, once composed with the original program, leads to the identification of the intended slice. Going through a number of examples, the paper suggests this approach may be an interesting, even if not completely general, alternative to slicing functional programs

Discovering coordination patterns

A large and growing amount of software systems rely on non-trivial coordination logic for making use of third party services or components. Therefore, it is of outmost importance to understand and capture rigorously this continuously growing layer of coordination as this will make easier not only the veri cation of such systems with respect to their original speci cations, but also maintenance, further development, testing, deployment and integration. This paper introduces a method based on several program analysis techniques (namely, dependence graphs, program slicing, and graph pattern analysis) to extract coordination logic from legacy systems source code. This process is driven by a series of pre-de ned coordination patterns and captured by a special purpose graph structure from which coordination speci cations can be generated in a number of di erent formalisms

Slicing for architectural analysis

Current software development often relies on non-trivial coordination logic for combining autonomous services, eventually running on different platforms. As a rule, however, such a coordination layer is strongly woven within the application at source code level. Therefore, its precise identification becomes a major methodological (and technical) problem and a challenge to any program understanding or refactoring process. The approach introduced in this paper resorts to slicing techniques to extract coordination data from source code. Such data are captured in a specific dependency graph structure from which a coordination model can be recovered either in the form of an Orc specification or as a collection of code fragments corresponding to the identification of typical coordination patterns in the system. Tool support is also discussed