The maximum degree & diameter-bounded subgraph and its applications
- Authors: Dekker, Anthony , Pérez-Rosés, Hebert , Pineda-Villavicencio, Guillermo , Watters, Paul
- Date: 2012
- Type: Text , Journal article
- Relation: Journal of Mathematical Modelling and Algorithms Vol. 11, no. 3 (2012), p. 249-268
- Full Text: false
- Reviewed:
- Description: We introduce the problem of finding the largest subgraph of a given weighted undirected graph (host graph), subject to constraints on the maximum degree and the diameter. We discuss some applications in security, network design and parallel processing, and in connection with the latter we derive some bounds for the order of the largest subgraph in host graphs of practical interest: the mesh and the hypercube. We also present a heuristic strategy to solve the problem, and we prove an approximation ratio for the algorithm. Finally, we provide some experimental results with a variety of host networks, which show that the algorithm performs better in practice than the prediction provided by our theoretical approximation ratio.
Synchronization properties of trees in the kuramoto model
- Authors: Dekker, Anthony , Taylor, Richard
- Date: 2013
- Type: Text , Journal article
- Relation: SIAM Journal on Applied Dynamical Systems Vol. 12, no. 2 (2013), p. 596-617
- Full Text:
- Reviewed:
- Description: We consider the Kuramoto model of coupled oscillators, specifically the case of tree networks, for which we prove a simple closed-form expression for the critical coupling. For several classes of tree, and for both uniform and Gaussian vertex frequency distributions, we provide tight closed-form bounds and empirical expressions for the expected value of the critical coupling. We also provide several bounds on the expected value of the critical coupling for all trees. Finally, we show that for a given set of vertex frequencies, there is a rearrangement of oscillator frequencies for which the critical coupling is bounded by the spread of frequencies. © 2013 Society for Industrial and Applied Mathematics.
- Description: C1
Heraclitus: A LFSR-based stream cipher with key dependent structure
- Authors: Colbert, Bernard , Dekker, Anthony , Batten, Lynn
- Date: 2011
- Type: Text , Conference proceedings
- Full Text: false
- Description: We describe Heraclitus as an example of a stream cipher that uses a 128 bit index string to specify the structure of each instance in real time: each instance of Heraclitus will be a stream cipher based on mutually clocked shift registers. © 2011 IEEE.
Undiagnosed cryptic diversity in small, microendemic frogs (Leptolalax) from the Central Highlands of Vietnam
- Authors: Rowley, Jodi , Tran, Dao , Frankham, Greta , Dekker, Anthony , Le, Duong , Nguyen, Truong , Dau, Vinh , Hoang, Huy
- Date: 2015
- Type: Text , Journal article
- Relation: PLoS ONE Vol. 10, no. 5 (2015), p. 1-21
- Full Text:
- Reviewed:
- Description: A major obstacle in prioritizing species or habitats for conservation is the degree of unrecognized diversity hidden within complexes of morphologically similar, "cryptic" species. Given that amphibians are one of the most threatened groups of organisms on the planet, our inability to diagnose their true diversity is likely to have significant conservation consequences. This is particularly true in areas undergoing rapid deforestation, such as Southeast Asia. The Southeast Asian genus Leptolalax is a group of small-bodied, morphologically conserved frogs that inhabit the forest-floor. We examined a particularly smallbodied and morphologically conserved subset, the Leptolalax applebyi group, using a combination of molecular, morphometric, and acoustic data to identify previously unknown diversity within. In order to predict the geographic distribution of the group, estimate the effects of habitat loss and assess the degree of habitat protection, we used our locality data to perform ecological niche modelling using MaxEnt. Molecular (mtDNA and nuDNA), acoustic and subtle morphometric differences revealed a significant underestimation of diversity in the L. applebyi group; at least two-thirds of the diversity may be unrecognised. Patterns of diversification and microendemism in the group appear driven by limited dispersal, likely due to their small body size, with several lineages restricted to watershed basins. The L. applebyi group is predicted to have historically occurred over a large area of the Central Highlands of Vietnam, a considerable portion of which has already been deforested. Less than a quarter of the remaining forest predicted to be suitable for the group falls within current protected areas. The predicted distribution of the L. applebyi group extends into unsurveyed watershed basins, each potentially containing unsampled diversity, some of which may have already been lost due to deforestation. Current estimates of amphibian diversity based on morphology alone are misleading, and accurate alpha taxonomy is essential to accurately prioritize conservation efforts. © 2015 Rowley et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Trophic cascades in 3D: network analysis reveals how apex predators structure ecosystems
- Authors: Wallach, Arian , Dekker, Anthony , Lurgi, Miguel , Montoya, Jose , Fordham, Damien , Ritchie, Euan , Fisher, Diana
- Date: 2017
- Type: Text , Journal article
- Relation: Methods in ecology and evolution Vol. 8, no. 1 (2017), p. 135-142
- Full Text: false
- Reviewed:
- Description: Summary Trophic cascade theory predicts that apex predators structure ecosystems by regulating mesopredator and herbivore abundance and behaviour. Studies on trophic cascades have typically focused on short linear chains of species interactions. A framework that integrates more realistic and complex interactions is needed to make broader predictions on ecosystem structuring. Network analysis is used to study food webs and other types of species interaction networks. These often comprise large numbers of species but rarely account for multiple interaction types and strengths. Here, we develop an intermediate complexity theoretical framework that allows specification of multiple interaction types and strengths for the study of trophic cascades. This ecological network is designed to suit data typically derived from field‐based studies. The trophic cascade network contains fewer nodes than food webs, but provides semi‐weighted directional links that enable different types of interactions to be included in a single model. We use this trophic cascade network model to explore how an apex predator shapes ecosystem structure in an Australian arid ecosystem. We compared two networks that contrasted in the dominance of an apex predator, the dingo (Canis dingo), using published results ranking the direction and strength of key interactions. Nodes and links interacted dynamically to shape these networks. We examined how changes to an apex predator population affect ecosystem structure through their direct and indirect influences on different components of this ecological community. Under strong apex predator influence, the network structure was denser and more complex, even and top‐down driven and dingo predation and soil commensalism formed denser interactive modules. Under weak apex predator influence (e.g. reflecting predator control), the resulting network structure was frayed, with mesopredator predation and grazing forming modules. Our study demonstrates that networks of intermediate complexity can provide a powerful tool for elucidating potential ecosystem‐wide effects of apex predators and predicting the consequences of management interventions such as predator control. Integrating trophic cascades, with their array of complex interactions, with the three‐dimensional structure of ecological networks, has the potential to reveal ‘ecological architecture’ that neither captures on its own.