Approximation Algorithms for Survivable Multicommodity Flow Problems with Applications to Network Design

Multicommodity flow (MF) problems have a wide variety of applications in areas such as VLSI circuit design, network design, etc., and are therefore very well studied. The fractional MF problems are polynomial time solvable while integer versions are NP-complete. However, exact algorithms to solve the fractional MF problems have high computational complexity. Therefore approximation algorithms to solve the fractional MF problems have been explored in the literature to reduce their computational complexity. Using these approximation algorithms and the randomized rounding technique, polynomial time approximation algorithms have been explored in the literature. In the design of high-speed networks, such as optical wavelength division multiplexing (WDM) networks, providing survivability carries great significance. Survivability is the ability of the network to recover from failures. It further increases the complexity of network design and presents network designers with more formidable challenges. In this work we formulate the survivable versions of the MF problems. We build approximation algorithms for the survivable multicommodity flow (SMF) problems based on the framework of the approximation algorithms for the MF problems presented in [1] and [2]. We discuss applications of the SMF problems to solve survivable routing in capacitated networks.

Incorporating Varying Test Costs and Fault Severities into Test Case Prioritization

Test case prioritization techniques schedule test cases for regression testing in an order that increases their ability to meet some performance goal. One performance goal, rate offault detection, measures how quickly faults are detected within the testing process. In previous work we provided a metric, APFD, for measuring rate of fault detection, and techniques for prioritizing test cases to improve APFD, and reported the results of experiments using those techniques. This metric and these techniques, however, applied only in cases in which test costs and fault severity are uniform. In this paper, we present a new metric for assessing the rate of fault detection of prioritized test cases, that incorporates varying test case and fault costs. We present the results of a case study illustrating the application of the metric. This study raises several practical questions that might arise in applying test case prioritization; we discuss how practitioners could go about answering these questions.

Observations on Chromosomes of Dicrostonyx torquatus stevensoni Nelson and Chromosomal Diversity in Varying Lemmings = Untersuchungen an den Chromosomen von Dicrostonyx torquatus stevensoni Nelson und chromosomale Unterschiede bei Halsbandlemmingen

English abstract: The cytogenetic characteristics of the varying lemming, Dicrostonyx torquatus stevensoni, (2n = 34), were investigated, and diploid chromosomal numbers were reported for four other nominal subspecies (exsul, nelsoni, richardsoni, and rubricatus) of the torquatus-group in North America. The diploid complements ranged from 30 to 44 chromosomes, and the fundamental number from 50 to 55. Chromosomal polymorphism was observed in all forms. In cross-breeding experiments, the mating of F1 progeny was not productive. The findings support the zoogeographic concept that populations of Dicrostonyx became fragmented or displaced southward during Würm time, with relict stocks persisting in unglaciated refugia or periglacial tundra. Speciation in the isolates led to chromosomal evolution, with the result that populations spreading from refugia in post-glacial time are reproductively isolated. The torquatus-group in North America appears to be a superspecies. German title: Untersuchungen an den Chromosomen von Dicrostonyx torquatus stevensoni Nelson und chromosomale Unterschiede bei Halsbandlemmingen German abstract: Die cytogenetischen Merkmale des Halsbandlemmings, Dicrostonyx torquatus stevensoni, (2n = 34) wurden eingehend untersucht, und für vier andere nordamerikanische Unterarten der torquatus-Gruppe wurden die somatischen Chromosomensätze festgestellt. Die Chromosomenzahl der untersuchten Populationen schwankte zwischen 30 und 44, der NF (Nombre Fondamental) zwischen 50 und 55. Zuchttiere der verschiedenen Populationen wurden erfolgreich gekreuzt, aber Sterilität der F1 Unterartbastarde war typisch. Die Halsbandlemminge wiesen Karyotypenverschiedenheiten auf, die sich durch Variationen des Robertsonschen Typus, Deletionen oder möglicherweise durch perizentrische Inversionen erklären. Die Ergebnisse sprechen dafür, daß das ursprüngliche Verbreitungsgebiet von Dicrostonyx in Nordamerika durch die letzte (Würm) Vereisung getrennt wurde, und daß die Reliktpopulationen die letzte Glazial-Phase in eisfreien Refugien oder in periglazialer Tundra überlebten, wo Karyotypevolution durch lokale Anpassungsbedürfnisse gefördert wurde. Die in der Postglazialzeit aus den Refugien sich verbreitenden Populationen von Dicrostonyx scheinen reproduktiv isoliert zu sein. Die torquatus-Gruppe in Nordamerika gilt also als Superspecies.