Hierarchical Approach for Survivable Network Design

A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. In this paper, we study the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. We develop a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization, and optimization. The approach decomposes the SND problem into two subproblems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. Since both subproblems are NP-hard, we develop effective optimization-based tabu search strategies that balance intensification and diversification to identify near-optimal solutions. To initiate this method, we develop two heuristic procedures that can yield good starting points. We test the combined approach on large-scale SND instances, and empirically assess the quality of the solutions vis-à-vis optimal values or lower bounds. On average, our hierarchical solution approach generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods), and our results demonstrate that the performance of the method is robust for a variety of problems with different size and connectivity characteristics.

Comparative Ultrastructure and Molecular Phylogeny of Selenidium melongena n. sp and S. terebellae Ray 1930 Demonstrate Niche Partitioning in Marine Gregarine Parasites (Apicomplexa)

Gregarine apicomplexans are a diverse group of single-celled parasites that have feeding stages (trophozoites) and gamonts that generally inhabit the extracellular spaces of invertebrate hosts living in marine, freshwater, and terrestrial environments. Inferences about the evolutionary morphology of gregarine apicomplexans are being incrementally refined by molecular phylogenetic data, which suggest that several traits associated with the feeding cells of gregarines arose by convergent evolution. The study reported here supports these inferences by showing how molecular data reveals traits that are phylogenetically misleading within the context of comparative morphology alone. We examined the ultrastructure and molecular phylogenetic positions of two gregarine species isolated from the spaghetti worm Thelepus japonicus: Selenidium terebellae Ray 1930 and S. melongena n. sp. The ultrastructural traits of S. terebellae were very similar to other species of Selenidium sensu stricto, such as having vermiform trophozoites with an apical complex, few epicytic folds, and a dense array of microtubules underlying the trilayered pellicle. By contrast, S. melongena n. sp. lacked a comparably discrete assembly of subpellicular microtubules, instead employing a system of fibrils beneath the cell surface that supported a relatively dense array of helically arranged epicytic folds. Molecular phylogenetic analyses of small subunit rDNA sequences derived from single-cell PCR unexpectedly demonstrated that these two gregarines are close sister species. The ultrastructural differences between these two species were consistent with the fact that S. terebellae infects the inner lining of the host intestines, and S. melongena n. sp. primarily inhabits the coelom, infecting the outside wall of the host intestine. Altogether, these data demonstrate a compelling case of niche partitioning and associated morphological divergence in marine gregarine apicomplexans. (C) 2014 Elsevier GmbH. All rights reserved.