PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Performance Evaluation of Distance-Hop Proportionality on Geometric Graph Models of Dense Sensor Networks

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes on a region in Euclidean space, e.g., the unit square. After deployment, the nodes self-organise into a mesh topology. In a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this paper, we analyse the performance of this approximation. We show that nodes with a certain hop distance from a fixed anchor node lie within a certain annulus with probability approach- ing unity as the number of nodes n → ∞. We take a uniform, i.i.d. deployment of n nodes on a unit square, and consider the geometric graph on these nodes with radius r(n) = c q ln n n . We show that, for a given hop distance h of a node from a fixed anchor on the unit square,the Euclidean distance lies within [(1−ǫ)(h−1)r(n), hr(n)],for ǫ > 0, with probability approaching unity as n → ∞.This result shows that it is more likely to expect a node, with hop distance h from the anchor, to lie within this an- nulus centred at the anchor location, and of width roughly r(n), rather than close to a circle whose radius is exactly proportional to h. We show that if the radius r of the ge- ometric graph is fixed, the convergence of the probability is exponentially fast. Similar results hold for a randomised lattice deployment. We provide simulation results that il- lustrate the theory, and serve to show how large n needs to be for the asymptotics to be useful.

Kinematics and dynamics of Jansen leg mechanism: A bond graph approach

The Jansen mechanism is a one degree-of-freedom, planar, 12-link, leg mechanism that can be used in mobile robotic applications and in gait analysis. This paper presents the kinematics and dynamics of the Jansen leg mechanism. The forward kinematics, accomplished using circle intersection method, determines the trajectories of various points on the mechanism in the chassis (stationary link) reference frame. From the foot point trajectory, the step length is shown to vary linearly while step height varies non-linearly with change in crank radius. A dynamic model for the Jansen leg mechanism is proposed using bond graph approach with modulated multiport transformers. For given ground reaction force pattern and crank angular speed, this model helps determine the motor torque profile as well as the link and joint stresses. The model can therefore be used to rate the actuator torque and in design of the hardware and controller for such a system. The kinematics of the mechanism can also be obtained from this dynamic model. The proposed model is thus a useful tool for analysis and design of systems based on the Jansen leg mechanism. (C) 2015 Elsevier B.V. All rights reserved.

Story Circle : Digital Storytelling Around the World

Story Circle is the first collection ever devoted to a comprehensive international study of the digital storytelling movement. Exploring subjects of central importance on the emergent and ever-shifting digital landscape-consumer-generated content, memory grids, the digital storytelling youth movement, and micro-documentary- Story Circle pinpoints who is telling what stories, where, on what terms, and what they look and sound like.

Multi-vehicles interaction graph model for cooperative collision warning system

Cooperative collision warning system for road vehicles, enabled by recent advances in positioning systems and wireless communication technologies, can potentially reduce traffic accident significantly. To improve the system, we propose a graph model to represent interactions between multiple road vehicles in a specific region and at a specific time. Given a list of vehicles in vicinity, we can generate the interaction graph using several rules that consider vehicle's properties such as position, speed, heading, etc. Safety applications can use the model to improve emergency warning accuracy and optimize wireless channel usage. The model allows us to develop some congestion control strategies for an efficient multi-hop broadcast protocol.

Accurate silhouette segmentation using motion detection and graph cuts

Acquiring accurate silhouettes has many applications in computer vision. This is usually done through motion detection, or a simple background subtraction under highly controlled environments (i.e. chroma-key backgrounds). Lighting and contrast issues in typical outdoor or office environments make accurate segmentation very difficult in these scenes. In this paper, gradients are used in conjunction with intensity and colour to provide a robust segmentation of motion, after which graph cuts are utilised to refine the segmentation. The results presented using the ETISEO database demonstrate that an improved segmentation is achieved through the combined use of motion detection and graph cuts, particularly in complex scenes.

Accurate silhouettes for surveillance : improved motion segmentation using graph cuts

Silhouettes are common features used by many applications in computer vision. For many of these algorithms to perform optimally, accurately segmenting the objects of interest from the background to extract the silhouettes is essential. Motion segmentation is a popular technique to segment moving objects from the background, however such algorithms can be prone to poor segmentation, particularly in noisy or low contrast conditions. In this paper, the work of [3] combining motion detection with graph cuts, is extended into two novel implementations that aim to allow greater uncertainty in the output of the motion segmentation, providing a less restricted input to the graph cut algorithm. The proposed algorithms are evaluated on a portion of the ETISEO dataset using hand segmented ground truth data, and an improvement in performance over the motion segmentation alone and the baseline system of [3] is shown.

Improved algebraic cryptanalysis of QUAD, Bivium and Trivium via graph partitioning on equation systems

We present a novel approach for preprocessing systems of polynomial equations via graph partitioning. The variable-sharing graph of a system of polynomial equations is defined. If such graph is disconnected, then the corresponding system of equations can be split into smaller ones that can be solved individually. This can provide a tremendous speed-up in computing the solution to the system, but is unlikely to occur either randomly or in applications. However, by deleting certain vertices on the graph, the variable-sharing graph could be disconnected in a balanced fashion, and in turn the system of polynomial equations would be separated into smaller systems of near-equal sizes. In graph theory terms, this process is equivalent to finding balanced vertex partitions with minimum-weight vertex separators. The techniques of finding these vertex partitions are discussed, and experiments are performed to evaluate its practicality for general graphs and systems of polynomial equations. Applications of this approach in algebraic cryptanalysis on symmetric ciphers are presented: For the QUAD family of stream ciphers, we show how a malicious party can manufacture conforming systems that can be easily broken. For the stream ciphers Bivium and Trivium, we nachieve significant speedups in algebraic attacks against them, mainly in a partial key guess scenario. In each of these cases, the systems of polynomial equations involved are well-suited to our graph partitioning method. These results may open a new avenue for evaluating the security of symmetric ciphers against algebraic attacks.

Development of a novel rolling-circle amplification technique to detect Banana streak virus which also discriminates between integrated and episomal virus sequences

Bananas are hosts to a large number of banana streak virus (BSV) species. However, diagnostic methods for BSV are inadequate because of the considerable genetic and serological diversity amongst BSV isolates and the presence of integrated BSV sequences in some banana cultivars which leads to false positives. In this study, a sequence non-specific, rolling-circle amplification (RCA) technique was developed and shown to overcome these limitations for the detection and subsequent characterisation of BSV isolates infecting banana. This technique was shown to discriminate between integrated and episomal BSV DNA, specifically detecting the latter in several banana cultivars known to contain episomal and/or integrated sequences of Banana streak Mysore virus (BSMyV), Banana streak OL virus (BSOLV) and Banana streak GF virus (BSGFV). Using RCA, the presence of BSMyV and BSOLV was confirmed in Australia, while BSOLV, BSGFV, Banana streak Uganda I virus (BSUgIV), Banana streak Uganda L virus (BSUgLV) and Banana streak Uganda M virus (BSUgMV) were detected in Uganda. This is the first confirmed report of episomally-derived BSUglV, BSUgLV and BSUgMV in Uganda. As well as its ability to detect BSV, RCA was shown to detect two other pararetroviruses, Sugarcane bacilliform virus in sugarcane and Cauliflower mosaic virus in turnip.

A participant’s response : recreating the circle with We Al-Li: a program for sharing and regeneration

Personal reflections on the We Al-Li Program

Full circle : the future of sustainable fashion manufacturing in New Zealand

Many fashion businesses in New Zealand have followed a global trend towards inexpensive off shore manufacturing. The transfer of the production of garments to overseas workers has had consequences for the wellbeing of local businesses, fashion designers and garment makers. The gradual decline of fashion manufacturing also appears to have resulted in a local fashion scene where many garments look the same in style, colour, fabric, cut and fit. The excitement of the past, where the majority of fashion designers established their own individuality through the cut and shape of the garments that they produced, may have been inadvertently lost in an effort to take advantage of cost savings achieved through mass production and manufacturing methods which are now largely unavailable in New Zealand. Consequently, a sustainable local fashion and manufacturing industry, with design integrity, seems further out of reach. This paper is focussed upon the thesis that the design and manufacture of a fashion garment, bearing in mind certain economic and practical restrictions at its inception, can contribute to a more sustainable fashion manufacturing industry in New Zealand.

Full Circle : a collection of prototypes

This exhibition engages with one of the key issues facing the fashion textiles industry in terms of future sustainability: that of the well being of fashion industry workers in Australia and New Zealand (people). This collection formed the basis of my honours dissertation (completed in New Zealand in 2008) which examines the contribution that design can make to sustainable manufacturing; particularly design for local production and consumption. An important aspect this work is the discussion of source, the work suggests that the made in China syndrome (in reference to the current state of over-consumerism in Australia and New Zealand) could be bought to a close through design to minimize waste and maximize opportunity for ‘people’: in this case both garment workers and the SMEs that employ them. The garments reflect the possibilities of focusing on a local approach that could be put into practice by a framework of SMEs that already exist. In addition the design process is highly transferrable and could be put into practice almost anywhere with minimal set up costs and a design ethos that progresses at the same pace as the skills of workers. This collection is a physical and conceptual embodiment of a source local/make local/sell local approach. The collection is an example of design that demonstrates that this is not an unrealistic ideal and is in fact possible through the development of a sustainable industry, in the sense of people, profit and planet, through adoption of a design process model that stops the waste at the source, by making better use of the raw materials and labour involved in making fashion garments. Although the focus of this research appears to centre on people and profit, this kind of source local/make local/sell local approach also has great benefits in terms of environmental sustainability.

An improved genetic algorithm and graph theory based method for optimal sectionalizer switch placement in distribution networks with DG

In this paper a new graph-theory and improved genetic algorithm based practical method is employed to solve the optimal sectionalizer switch placement problem. The proposed method determines the best locations of sectionalizer switching devices in distribution networks considering the effects of presence of distributed generation (DG) in fitness functions and other optimization constraints, providing the maximum number of costumers to be supplied by distributed generation sources in islanded distribution systems after possible faults. The proposed method is simulated and tested on several distribution test systems in both cases of with DG and non DG situations. The results of the simulations validate the proposed method for switch placement of the distribution network in the presence of distributed generation.

Graph rigidity for near-coplanar structure from motion

Recent algorithms for monocular motion capture (MoCap) estimate weak-perspective camera matrices between images using a small subset of approximately-rigid points on the human body (i.e. the torso and hip). A problem with this approach, however, is that these points are often close to coplanar, causing canonical linear factorisation algorithms for rigid structure from motion (SFM) to become extremely sensitive to noise. In this paper, we propose an alternative solution to weak-perspective SFM based on a convex relaxation of graph rigidity. We demonstrate the success of our algorithm on both synthetic and real world data, allowing for much improved solutions to marker less MoCap problems on human bodies. Finally, we propose an approach to solve the two-fold ambiguity over bone direction using a k-nearest neighbour kernel density estimator.