Quantitative and molecular genetics of juvenile wood traits in radiata and slash/Caribbean pines.

The Juvenile Wood Initiative (JWI) project has been running successfully since July 2003 under a Research Agreement with FWPA and Letters of Association with the consortium partners STBA (Southern Tree Breeding Association), ArborGen and FPQ (Forestry Plantations Queensland). Over the last five and half years, JWI scientists in CSIRO, FPQ, and STBA have completed all 12 major milestones and 28 component milestones according to the project schedule. We have made benchmark progress in understanding the genetic control of wood formation and interrelationships among wood traits. The project has made 15 primary scientific findings and several results have been adopted by industry as summarized below. This progress was detailed in 10 technical reports to funding organizations and industry clients. Team scientists produced 16 scientific manuscripts (8 published, 1 in press, 2 submitted, and several others in the process of submission) and 15 conference papers or presentations. Primary Scientific Findings. The 15 major scientific findings related to wood science, inheritance and the genetic basis of juvenile wood traits are: 1. An optimal method to predict stiffness of standing trees in slash/Caribbean pine is to combine gravimetric basic density from 12 mm increment cores with a standing tree prediction of MoE using a time of flight acoustic tool. This was the most accurate and cheapest way to rank trees for breeding selection for slash/Caribbean hybrid pine. This method was also recommended for radiata pine. 2. Wood density breeding values were predicted for the first time in the STBA breeding population using a large sample of 7,078 trees (increment cores) and it was estimated that selection of the best 250 trees for deployment will produce wood density gains of 12.4%. 3. Large genetic variation for a suite of wood quality traits including density, MFA, spiral grain, shrinkage, acoustic and non-acoustic stiffness (MoE) for clear wood and standing trees were observed. Genetic gains of between 8 and 49% were predicted for these wood quality traits with selection intensity between 1 to 10% for radiata pine. 4. Site had a major effect on juvenile-mature wood transition age and the effect of selective breeding for a shorter juvenile wood formation phase was only moderate (about 10% genetic gain with 10% selection intensity, equivalent to about 2 years reduction of juvenile wood). 5. The study found no usable site by genotype interactions for the wood quality traits of density, MFA and MoE for both radiata and slash/Caribbean pines, suggesting that assessment of wood properties on one or two sites will provide reliable estimates of the genetic worth of individuals for use in future breeding. 6. There were significant and sizable genotype by environment interactions between the mainland and Tasmanian regions and within Tasmania for DBH and branch size. 7. Strong genetic correlations between rings for density, MFA and MoE for both radiata and slash/Caribbean pines were observed. This suggests that selection for improved wood properties in the innermost rings would also result in improvement of wood properties in the subsequent rings, as well as improved average performance of the entire core. 8. Strong genetic correlations between pure species and hybrid performance for each of the wood quality traits were observed in the hybrid pines. Parental performance can be used to identify the hybrid families which are most likely to have superior juvenile wood properties of the slash/Caribbean F1 hybrid in southeast Queensland. 9. Large unfavourable genetic correlations between growth and wood quality traits were a prominent feature in radiata pine, indicating that overcoming this unfavourable genetic correlation will be a major technical issue in progressing radiata pine breeding. 10. The project created the first radiata pine 18 k cDNA microarray and generated 5,952 radiata pine xylogenesis expressed sequence tags (ESTs) which assembled into 3,304 unigenes. 11. A total of 348 genes were identified as preferentially expressed genes in earlywood or latewood while a total of 168 genes were identified as preferentially expressed genes in either juvenile or mature wood. 12. Juvenile earlywood has a distinct transcriptome relative to other stages of wood development. 13. Discovered rapid decay of linkage disequilibrium (LD) in radiata pine with LD decaying to approximately 50% within 1,700 base pairs (within a typical gene). A total of 913 SNPS from sequencing 177,380 base pairs were identified for association genetic studies. 14. 149 SNPs from 44 genes and 255 SNPs from a further 51 genes (total 95 genes) were selected for association analysis with 62 wood traits, and 30 SNPs were shortlisted for their significant association with variation of wood quality traits (density, MFA and MoE) with individual significant SNPs accounting for between 1.9 and 9.7% of the total genetic variation in traits. 15. Index selection using breeding objectives was the most profitable selection method for radiata pine, but in the long term it may not be the most effective in dealing with negative genetic correlations between wood volume and quality traits. A combination of economic and biological approaches may be needed to deal with the strong adverse correlation.

Kidney Induction: control by Notch, Wnt and GDNF/Ret signalling

The permanent mammalian kidney (metanephros) develops as a result of complex reciprocal tissue interactions between a ureteric epithelium and the renal mesenchyme. The overall goal of the research in this thesis was to gain data that will eventually help in elucidating the formation of congenital renal malformations. The experiments in my thesis aimed to reveal the mechanisms by which Notch, Wnt and GDNF/Ret signalling pathways regulate the development of functional kidney. The function of Notch pathway was studied by a transgenic mouse model, where it was shown that overactivation of Notch signalling disturbs kidney development and alters the expression of Gdnf and Ret/GFRa1. This indicates that Notch signalling interplays with GDNF/Ret in the regulation of the primary ureteric budding and its subsequent branching. The data also suggested that strict spatio-temporal regulation of these two pathways is required for determination of ureteric tip-identity, which appeared to be crucial for the branch formation. The function of Wnt signalling in the ureteric morphogenesis was studied by in vivo and in vitro methods to show that a canonical pathway is required for ureteric branching. Stabilisation and deletion of the canonical pathway mediator, b-catenin specifically in the ureteric epithelium result in renal aplasia/hypodysplasia. These defects originate from severe blockage of ureteric branching due to the disrupted Ret signalling. Consequently, ureteric tip specific markers are lost and ureteric stalk identity is expanded throughout the whole epithelium. Thus, the data demonstrates that the Wnt/b-catenin pathway plays an essential role in the patterning and branching of the ureteric epithelium. A novel in vitro method was generated and utilised in nephron induction studies to reveal the mechanisms through which nephrogenesis is induced. Transient GSK3 inhibition results in stabilisation of b-catenin in the isolated renal mesenchyme, which efficiently triggers nephron formation. Also genetic stabilisation of b-catenin specifically in the mesenchyme results in spontaneous nephrogenesis. The results show that activation of the canonical Wnt pathway is sufficient to initiate nephrogenesis, and suggest that this pathway mediates the nephron induction in murine kidney mesenchymes. Taken together, this thesis demonstrates Notch and Wnt signalling pathways as novel regulators of ureteric branching morphogenesis, and that activation of the canonical Wnt pathway is sufficient for nephron induction. The studies also indicate that the Notch and Wnt pathways cross-talk with GDNF/Ret signalling in the patterning of ureteric epithelium.

Quantum supersymmetric generalisation of Bogomolnyi bounds

We review here classical Bogomolnyi bounds, and their generalisation to supersymmetric quantum field theories by Witten and Olive. We also summarise some recent work by several people on whether such bounds are saturated in the quantised theory.

Regulation of strawberry growth and development

Strawberries (Fragaria sp.) are adapted to diverse environmental conditions from the tropics to about 70ºN, so different responses to environmental conditions can be found. Most genotypes of garden strawberry (F. x ananassa Duch.) and woodland strawberry (F. vesca L.) are short-day (SD) plants that are induced to flowering by photoperiods under a critical limit, but also various photoperiod x temperature interactions can be found. In addition, continuously flowering everbearing (EB) genotypes are found. In addition to flowering, axillary bud differentiation in strawberry is regulated by photoperiod. In SD conditions, axillary buds differentiate to rosette-like structures called "branch crowns", whereas in long-day conditions (LD) they form runners, branches with 2 long internodes followed by a daughter plant (leaf rosette). The number of crown branches determines the yield of the plant, since inflorescences are formed from the apical meristems of the crown. Although axillary bud differentiation is an important developmental process in strawberries, its environmental and hormonal regulation has not been characterized in detail. Moreover, the genetic mechanisms underlying axillary bud differentiation and regulation of flowering time in these species are almost completely unresolved. These topics have been studied in this thesis in order to enhance strawberry research, cultivation and breeding. The results showed that 8-12 SD cycles suppressed runner initiation from the axillary buds of the garden strawberry cv. Korona with the concomitant induction of crown branching, and 3 weeks of SD was sufficient for the induction of flowering in the main crown. Furthermore, a second SD treatment given a few weeks after the first SD period can be used to induce flowering in the primary branch crowns and to induce the formation of secondary branches. Thus, artificial SD treatments effectively stimulate crown branching, providing one means for the increase of cropping (yield) potential in strawberry. It was also shown by growth regulation applications, quantitave hormone analysis and gene expression analysis that gibberellin (GA) is one of the key signals involved in the photoperiod control of shoot differentiation. The results indicate that photoperiod controls GA activity specifically in axillary buds, thereby determining bud fate. It was further shown that chemical control of GA biosynthesis by prohexadione-calcium can be utilized to prevent excessive runner formation and induce crown branching in strawberry fields. Moreover, ProCa increased berry yield up to 50%, showing that it is an easier and more applicable alternative to artificial SD treatments for controlling strawberry crown development and yield. Finally, flowering gene pathways in Fragaria were explored by searching for homologs of 118 Arabidopsis thaliana flowering-time genes. In total, 66 gene homologs were identified, and they distributed to all known flowering pathways, suggesting the presence of these pathways also in strawberry. Expression analysis of selected genes revealed that the mRNA of putative floral identity gene APETALA1 accumulated in the shoot apex of the EB genotype after the induction of flowering, whereas it was absent in vegetative SD genotype, indicating the usefulness of this gene product as the marker of floral initiation. The present data enables the further exploration of strawberry flowering pathways with genetic transformation, gene mapping and transcriptomics methods.

DNA-based detection and characterisation of strictly anaerobic beer-spoilage bacteria

Megasphaera cerevisiae, Pectinatus cerevisiiphilus, Pectinatus frisingensis, Selenomonas lacticifex, Zymophilus paucivorans and Zymophilus raffinosivorans are strictly anaerobic Gram-stain-negative bacteria that are able to spoil beer by producing off-flavours and turbidity. They have only been isolated from the beer production chain. The species are phylogenetically affiliated to the Sporomusa sub-branch in the class "Clostridia". Routine cultivation methods for detection of strictly anaerobic bacteria in breweries are time-consuming and do not allow species identification. The main aim of this study was to utilise DNA-based techniques in order to improve detection and identification of the Sporomusa sub-branch beer-spoilage bacteria and to increase understanding of their biodiversity, evolution and natural sources. Practical PCR-based assays were developed for monitoring of M. cerevisiae, Pectinatus species and the group of Sporomusa sub-branch beer spoilers throughout the beer production process. The developed assays reliably differentiated the target bacteria from other brewery-related microbes. The contaminant detection in process samples (10 1,000 cfu/ml) could be accomplished in 2 8 h. Low levels of viable cells in finished beer (≤10 cfu/100 ml) were usually detected after 1 3 d culture enrichment. Time saving compared to cultivation methods was up to 6 d. Based on a polyphasic approach, this study revealed the existence of three new anaerobic spoilage species in the beer production chain, i.e. Megasphaera paucivorans, Megasphaera sueciensis and Pectinatus haikarae. The description of these species enabled establishment of phenotypic and DNA-based methods for their detection and identification. The 16S rRNA gene based phylogenetic analysis of the Sporomusa sub-branch showed that the genus Selenomonas originates from several ancestors and will require reclassification. Moreover, Z. paucivorans and Z. raffinosivorans were found to be in fact members of the genus Propionispira. This relationship implies that they were carried to breweries along with plant material. The brewery-related Megasphaera species formed a distinct sub-group that did not include any sequences from other sources, suggesting that M. cerevisiae, M. paucivorans and M. sueciensis may be uniquely adapted to the brewery ecosystem. M. cerevisiae was also shown to exhibit remarkable resistance against many brewery-related stress conditions. This may partly explain why it is a brewery contaminant. This study showed that DNA-based techniques provide useful tools for obtaining more rapid and specific information about the presence and identity of the strictly anaerobic spoilage bacteria in the beer production chain than is possible using cultivation methods. This should ensure financial benefits to the industry and better product quality to customers. In addition, DNA-based analyses provided new insight into the biodiversity as well as natural sources and relations of the Sporomusa sub-branch bacteria. The data can be exploited for taxonomic classification of these bacteria and for surveillance and control of contaminations.

Puccinia psidii in Queensland, Australia: disease symptoms, distribution and impact

Puccinia psidii has long been considered a significant threat to Australian plant industries and ecosystems. In April 2010, P. psidii was detected for the first time in Australia on the central coast of New South Wales (NSW). The fungus spread rapidly along the east coast and in December 2010 was found in Queensland (Qld) followed by Victoria a year later. Puccinia psidii was initially restricted to the southeastern part of Qld but spread as far north as Mossman. In Qld, 48 species of Myrtaceae are considered highly or extremely susceptible to the disease. The impact of P. psidii on individual trees and shrubs has ranged from minor leaf spots, foliage, stem and branch dieback to reduced fecundity. Tree death, as a result of repeated infection, has been recorded for Rhodomyrtus psidioides. Rust infection has also been recorded on flower buds, flowers and fruits of 28 host species. Morphological and molecular characteristics were used to confirm the identification of P. psidii from a range of Myrtaceae in Qld and compared with isolates from NSW and overseas. A reconstructed phylogeny based on the LSU and SSU regions of rDNA did not resolve the familial placement of P. psidii, but indicated that it does not belong to the Pucciniaceae. Uredo rangelii was found to be con-specific with all isolates of P. psidii in morphology, ITS and LSU sequence data, and host range.

Walter, Greta and Karl Loewenstein Collection. 1821-2004 Bulk: 1933-1989

This collection holds papers of members of the Loewenstein family, especially Walter and Karl Loewenstein. Among the papers here are examples of Walter Loewenstein's writing, documentation of life in Rietberg in Westphalia (Germany) during the late 1930s and early 1940s, and correspondence concerning the fate of several family members during this time. Papers relating to Karl Loewenstein focus on his wartime activities. The genealogy of the Brandenstein family is also represented here along with a few papers of other family members. The collection consists of unpublished manuscripts, correspondence, photographs, official and restitution documentation, notebooks and notes, genealogical research, and fliers.

Analysis and prevention of extreme vibration in high speed craft - A research framework

Extreme vibration has been reported for small, high speed craft in the maritime sector, with performance and health threatening effects on boat operators and crew. Musculoskeletal injuries are an enduring problem for high speed craft passengers. Spinal or joint injuries and neurological disorders may occur from repetitive pounding over rough water, continued vibration and single impact events. The risk from whole body vibration (WBV) induced through the small vessels mainly depends on time spent on the craft, which can’t be changed in a military scenario; as well as the number of shocks and jolts, and their magnitude and frequency. In the European Union for example, physical agents directives require all employers to control exposure to a number of physical agents including noise and vibration. The EC Vibration Directive 2002/44/EC then sets out regulations for the control of health and safety risks from the exposure of workers to hand arm vibration (HAV) and WBV in the workplace. Australia has exposure standards relating to WBV, AS 2670.1-2001 – Evaluation of human exposure to whole body vibration. This standard is identical to the ISO 2631-1:1997, Mechanical vibration and shock – Evaluation of human exposure to whole-body vibration. Currently, none of the jurisdictions in Australia have specific regulations for vibration exposures in workplaces. However vibration is mentioned to varying degrees in their general regulations, codes of practice and guidance material. WBV on high speed craft is normally caused by “continuous 'hammering' from short steep seas or wind against tide conditions. Shock on High Speed Craft is usually caused by random impacts. Military organisations need the knowledge to make informed decisions regarding their marine operations, compliance with legislation and potentially harmful health effects, and develop and implement appropriate counter-measures. Marine case studies in the UK such as published MAIB (Marine Accident Investigation Branch) reports show injuries that have occurred in operation, and subsequent MCA (Maritime Coastguard Agency) guidance is provided (MGN 436 (M+F), WHOLE-BODY VIBRATION: Guidance on Mitigating Against the Effects of Shocks and Impacts on Small Vessels. MCA, 2011). This paper proposes a research framework to study the origin, impact and pathways for prevention of WBV in small, high speed craft in a maritime environment.

Floristic composition and pasture condition of Aristida/Bothriochloa pastures in central Queensland. II. Soil and pasture condition interactions

Sustainable management of native pastures requires an understanding of what the bounds of pasture composition, cover and soil surface condition are for healthy pastoral landscapes to persist. A survey of 107 Aristida/Bothriochloa pasture sites in inland central Queensland was conducted. The sites were chosen for their current diversity of tree cover, apparent pasture condition and soil type to assist in setting more objective bounds on condition ‘states’ in such pastures. Assessors’ estimates of pasture condition were strongly correlated with herbage mass (r = 0.57) and projected ground cover (r = 0. 58), and moderately correlated with pasture crown cover (r = 0.35) and tree basal area (r = 0.32). Pasture condition was not correlated with pasture plant density or the frequency of simple guilds of pasture species. The soil type of Aristida/Bothriochloa pasture communities was generally hard-setting, low in cryptogam cover but moderately covered with litter and projected ground cover (30–50%). There was no correlation between projected ground cover of pasture and estimated ground-level cover of plant crowns. Tree basal area was correlated with broad categories of soil type, probably because greater tree clearing has occurred on the more fertile, heavy-textured clay soils. Of the main perennial grasses, some showed strong soil preferences, for example Tripogon loliiformis for hard-setting soils and Dichanthium sericeum for clays. Common species, such as Chrysopogon fallax and Heteropogon contortus, had no strong soil preference. Wiregrasses (Aristida spp.) tended to be uncommon at both ends of the estimated pasture condition scale whereas H. contortus was far more common in pastures in good condition. Sedges (Cyperaceae) were common on all soil types and for all pasture condition ratings. Plants identified as increaser species were Tragus australianus, daisies (Asteraceae) and potentially toxic herbaceous legumes such as Indigofera spp. and Crotalaria spp. Pasture condition could not be reliably predicted based on the abundance of a single species or taxon but there may be scope for using integrated data for four to five ecologically contrasting plants such as Themeda triandra with daisies, T. loliiformis and flannel weeds (Malvaceae).

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Regional Integration and the State : The Changing Nature of Sovereignty in Southern Africa and Europe

The study explores the role of the state in regional integration processes. The question is approached through theoretical discussion and two case-studies - SADC (Southern African Development Community) and the EU. The main research question of the study is, what are the possibilities and problems of the integration process in Southern Africa and how do they differ from the possibilities and problems of the integration process in Europe. The undelrying question of the study is why do states decide to participate in an integration process where they have to limit their sovereignty. Review of the theoretical discussion of the integration studies shows that the integration process is affected by several factors on different levels of the international system. But the state plays a central role in integration processes - integration processes are inititated and carried on by the participatig states. The European integration process shows that the interests of the state can change over time. At the beginning of the integration process, the objective was to strengthen participating states. Later EU member states have decided that it is in their interest to deepen the process even if it has meant limitation of their sovereignty. The determinant factor has been that the member states have considered it to be in their interst to deepen the process. In Southern Africa the integration process is only at the beginning. SADC aims to establish a free trade area by 2008. The biggest challenge is how to implement the integration process so that it benefits all member states in a region that is economically dominated by South Africa. In practice this can be achieved through establishment of corrective mechanisms, which ensure equitable distribution of benefits. This would require deeper integration and South Africa to adapt responsibility towards its regional partners. African integration processes in general have not been as successful as for example the EU. African states have been reluctant to limit their sovereignty in favour of regional organisations.This can be explained by the differences between European and African states. The EU member states have been democracies while African states have been characterised by concentration of power in the executive branch. Furthermore the political systems in Africa have been characterised by vertical clientelist reltionships. As a result it has not been in the interest of the political elite to limit the state sovereignty in favour of regional organisations. In recent years SADC has been relatively succesful in its integration process and reforms, but a lot remains to be done before the implementation of the free trade area can be succesful. The institutional structure and treaties of SADC differ from the structures of the EU. Member states are the main actors of the integration processes. Their differences are reflected in the process and produce different kinds of integration in different parts of the world.

Automatic Path Planning and Control Design for Autonomous Landing of UAVs using Dynamic Inversion

In this paper a nonlinear control has been designed using the dynamic inversion approach for automatic landing of unmanned aerial vehicles (UAVs), along with associated path planning. This is a difficult problem because of light weight of UAVs and strong coupling between longitudinal and lateral modes. The landing maneuver of the UAV is divided into approach, glideslope and flare. In the approach UAV aligns with the centerline of the runway by heading angle correction. In glideslope and flare the UAV follows straight line and exponential curves respectively in the pitch plane with no lateral deviations. The glideslope and flare path are scheduled as a function of approach distance from runway. The trajectory parameters are calculated such that the sink rate at touchdown remains within specified bounds. It is also ensured that the transition from the glideslope to flare path is smooth by ensuring C-1 continuity at the transition. In the outer loop, the roll rate command is generated by assuring a coordinated turn in the alignment segment and by assuring zero bank angle in the glideslope and flare segments. The pitch rate command is generated from the error in altitude to control the deviations from the landing trajectory. The yaw rate command is generated from the required heading correction. In the inner loop, the aileron, elevator and rudder deflections are computed together to track the required body rate commands. Moreover, it is also ensured that the forward velocity of the UAV at the touch down remains close to a desired value by manipulating the thrust of the vehicle. A nonlinear six-DOF model, which has been developed from extensive wind-tunnel testing, is used both for control design as well as to validate it.

On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

A unit cube in k dimensions (k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), a(i) + 1] on the real line. A graph G on n nodes is said to be representable as the intersection of k-cubes (cube representation in k dimensions) if each vertex of C can be mapped to a k-cube such that two vertices are adjacent in G if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G denoted as cub(G) is the minimum k for which G can be represented as the intersection of k-cubes. An interesting aspect about cubicity is that many problems known to be NP-complete for general graphs have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We give an O(bw . n) algorithm to compute the cube representation of a general graph G in bw + 1 dimensions given a bandwidth ordering of the vertices of G, where bw is the bandwidth of G. As a consequence, we get O(Delta) upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and cocomparability graphs which have O(Delta) bandwidth. Thus we have: 1. cub(G) <= 3 Delta - 1, if G is an AT-free graph. 2. cub(G) <= 2 Delta + 1, if G is a circular-arc graph. 3. cub(G) <= 2 Delta, if G is a cocomparability graph. Also for these graph classes, there axe constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with O(Delta) width. We can thus generate the cube representation of such graphs in O(Delta) dimensions in polynomial time.

DMT of Multi-hop Cooperative Networks-Part II: Layered and Multi-Antenna Networks

We consider single-source, single-sink (ss-ss) multi-hop relay networks, with slow-fading Rayleigh links. This two part paper aims at giving explicit protocols and codes to achieve the optimal diversity-multiplexing tradeoff (DMT) of two classes of multi-hop networks: K-parallel-path (KPP) networks and Layered networks. While single-antenna KPP networks were the focus of the first part, we consider layered and multi-antenna networks in this second part. We prove that a linear DMT between the maximum diversity d(max). and the maximum multiplexing gain of 1 is achievable for single-antenna fully-connected layered networks under the half-duplex constraint. This is shown to be equal to the optimal DMT if the number of relaying layers is less than 4. For the multiple-antenna case, we provide an achievable DMT, which is significantly better than known lower bounds for half duplex networks. Along the way, we compute the DMT of parallel MIMO channels in terms of the DMT of the component channel. For arbitrary ss-ss single-antenna directed acyclic networks with full-duplex relays, we prove that a linear tradeoff between maximum diversity and maximum multiplexing gain is achievable using an amplify-and-forward (AF) protocol. Explicit short-block-length codes are provided for all the proposed protocols. Two key implications of the results in the two-part paper are that the half-duplex constraint does not necessarily entail rate loss by a factor of two as previously believed and that simple AN protocols are often sufficient to attain the best possible DMT.