bluuebunny/crossref_metadata_2025 huggingface dataset:
Metabolomic approach to identifying bioactive compounds in berries: Advances toward fruit nutritional enhancement
Authors: Stewart Derek , McDougall Gordon J. , Sungurtas Julie , Verrall Susan , Graham Julie , Martinussen Inger
Published: May 2007

Plant polyphenolics continue to be the focus of attention with regard to their putative impact on human health. An increasing and ageing human population means that the focus on nutrition and nutritional enhancement or optimisation of our foodstuffs is paramount. Using the raspberry as a model, we have shown how modern metabolic profiling approaches can be used to identify the changes in the level of beneficial polyphenolics in fruit breeding segregating populations and how the level of these components is determined by genetic and/or environmental control. Interestingly, the vitamin C content appeared to be significantly influenced by environment (growth conditions) whilst the content of the polyphenols such as cyanidin, pelargonidin and quercetin glycosides appeared much more tightly regulated, suggesting a rigorous genetic control. Preliminary metabolic profiling showed that the fruit polyphenolic profiles divided into two gross groups segregating on the basis of relative levels of cyanidin‐3‐sophoroside and cyanidin‐3‐rutinoside, compounds implicated as conferring human health benefits.
Synthesis of modulation insensitive N‐path filters
Authors: Chang S. , Declaris N. , Newcomb R. W.
Published: May 2007

Through the intermediary of state‐variable equations, realization of an N‐path filter from a prescribed transfer function is obtained. An equivalence is found which shows how passive RC circuits incorporating time‐variable gyrators can be used to realize N‐path filters. It is also proved possible to realize any stable transfer function as an N‐path filter structure and that the system is insensitive to the frequency of the multiplying signals or the frequency of the gyration conductance.

„Listen again to this. I have seen moonlight Sometimes the statues leaning over like reeds In the middle of living fruit, – the statues”︁[1,p. 95].
The network equilibrium problem in integers
Authors: Rosenthal R. W.
Published: May 2007

In the usual approach to network equilibrium models, the flow variables are modeled as continuous. When the problem under study involves discrete decision makers each controlling an indivisible unit of flow, another approach is called for. We treat the problem as an n‐person noncooperative game with pure strategies corresponding to feasible paths through the network. It is shown that pure‐strategy Nash equilibria exist and that any solution to an integer‐variable analogue of the usual network equilibrium model is such a Nash equilibrium. It is also shown that when individuals can control more than a single unit of flow and want to minimize the sum of their costs, pure‐strategy Nash equilibria do not necessarily exist.
The Capacitated Minimum Spanning Tree
Authors: Chandy K. M. , Lo Tachen
Published: May 2007

The capacitated minimum spanning tree is an offspring of the minimum spanning tree and network flow problems. It has application in the design of multipoint linkages in elementary teleprocessing tree networks. Some theorems are used in conjunction with Little's branch and bound algorithm to obtain optimal solutions. Computational results are provided to show that the problem is tractable.
Network properties of the ARPA computer network
Authors: Frank H. , Chou W.
Published: May 2007

The ARPA Computer Network, which today links over 60 host computers in more than 40 different locations is a significant advance both in computer systems and data communications. The ARPANET uses a communication technique called packet switching to dynamically select message routes through the network. In this paper, we discuss a number of important properties of the network as well as the techniques used to identify these properties. Among the topics discussed are ARPANET growth, performance sensitivity to traffic variations, incremental costs for adding capacity and new sites, peak throughput costs, and network reliability.
Minimum cuts and related problems
Authors: Picard J. C. , Ratliff H. D.
Published: May 2007

This paper is concerned with an integer programming characterization of a cut in a network. This characterization provides a fundamental equivalence between directed pseudosymmetric networks and undirected networks. It also identifies a class of problems which can be solved as minimum cut problems on a network.
A necessary condition for the existence of a circuit of any specified length
Authors: Gehner K. R.
Published: May 2007

A necessary condition for the existence of a circuit of any specified length in a connected planar graph is developed and several applications of this result are given. This necessary condition is a direct generalization of the Kosyrev‐Grinberg condition for the existence of a Hamiltonian circuit in a planar graph.
Maximum flow in probabilistic graphs‐the discrete case
Authors: Evans J. R.
Published: May 2007

Frank and Frisch have considered the problem of determining the maximum flow probability distribution in networks where each branch has capacity that is a continuous random variable. In this paper, we consider the branch capacity distributions to be discrete and investigate some theoretical properties of the problem under this assumption.
Iterative methods for determining the k shortest paths in a network
Authors: Shier D. R.
Published: May 2007

This paper presents and develops an algebraic structure for determining the k shortest paths from a given node to all other nodes of a network. Three new methods for calculating such k shortest path information are examined and compared. These methods are based on a fairly strong analogy which exists between the solution of such network problems and traditional techniques for solving linear equations. On the basis of both theoretical and computational evidence, one of the three methods is seen to offer an extremely effective procedure for finding the k shortest paths from a given node in a network.
Rectilinear steiner trees: Efficient special‐case algorithms
Authors: Aho A. V. , Garey M. R. , Hwang F. K.
Published: May 2007

A minimal rectilinear Steiner tree for a set A of points in the plane is a tree which interconnects A using horizontal and vertical lines of shortest possible total length. Such trees have potential application to wire layout for printed circuits. Unfortunately, at present no practical algorithm is known for constructing these trees in general. We present two algorithms, each requiring a number of operations proportional to only a low degree polynomial in the number of points to be interconnected, for the special cases in which all the points of A lie on a small number of parallel lines or on the boundary of a rectangle.
A problem on blocking probabilities in connecting networks
Authors: Chung F. R. K. , Hwang F. K.
Published: May 2007

We begin with a three‐stage linear graph in which the first stage has a single node u and the third stage a single node v. The second stage has k independent nodes, each of which is connected by one link to u and to v. In general, we can form a (2n+1)‐stage linear graph recursively by letting each node in the second stage of a three‐stage linear graph be replaced by a copy of a (2n‐1)‐stage linear graph.

A link can either be in the busy state or the idle state. We assume that the states of each link are mutually independent and that any link between stage i and stage i + 1 has the probability I.z of being idle. The nodes u and v are said to be connectable if there exists at least one path from u to v with no busy link. Let P(u, v) denote the probability of such a path existing. Further, let N(2n+1, k) denote the set of (2n+1)‐stage linear graphs whose center stages have k nodes.

In this paper, we determine the size of N(2n+1, k). We also give the linear graph in N(2n+1, k) which has the largest P(u, v) and the one which has the smallest. We then show how our results apply to a recent problem in connecting networks.
A fast algorithm for reliability calculations in sparse networks
Authors: Spyratos N. , Bowen A.
Published: May 2007

The calculation of terminal reliability in other than simple series‐parallel networks takes time exponential in the size of the network. A method is presented for reducing network size by decomposing the network into subnetworks. Terminal reliability is obtained from calculations in the subnetworks. As the efficiency of the method depends on the network decomposition, some simple rules for selecting ‘good’ decompositions are presented.

The method yields approximate values of terminal reliability. In sparse networks, however, the approximation is very satisfactory. Further, if the network decomposition satisfies certain conditions, exact values are obtained. Although the method assumes undirected links and perfectly reliable nodes, it can be easily extended to include directed links and failing nodes.
Graph substitution and set packing polytopes
Authors: Balas E. , Zemel E.
Published: May 2007

Facets of the set packing polytope provide strong cutting planes for set packing and partitioning problems. Set packing polytopes are in a one‐to‐one correspondence with graphs. The facets of P(G), the set packing polytope associated with the graph G, are related to certain subgraphs of G. Of particular interest are those subgraphs G′ which are facet producing, i.e., which give rise to facets of P(G′) that cannot be obtained by lifting a facet of P(G′ ‐ {x}), for any vertex x of G′. In this paper we characterize the facets of the set packing polytopes associated with the class of graphs obtained by Chvátal's substitution procedure, and give necessary and sufficient conditions for these graphs to be facet‐producing.
Network topology and integral multicommodity flow problems
Authors: Evans J. R. , Jarvis J. J.
Published: May 2007

In this paper we investigate the nature of integer solutions to multicommodity network flow problems from a graphtheoretic viewpoint. A sufficient condition for unimodularity is developed that is based upon the topological characteristics of the associated graph, and the results are applied to certain well‐structured examples.
An assignment routing problem
Authors: Russell R. , Igo W.
Published: May 2007

ABSTRACT

This paper examines a routing design problem in which the objective is to assign customer demand points to days of the week in order to solve the resulting node routing problems over the entire week most effectively. The emphasis is on obtaining approximate solutions for this type of combinatorial problem. Several heuristics are developed and tested on a large scale refuse collection problem. Computational results, as well as a discussion of expected benefits, are presented.
On the construction of balanced switching networks
Authors: Hwang F. K. , Lin S.
Published: May 2007

A balanced switching network is a multistage switching network where all channel graphs G(α, β) (the union of all paths from the input switch α to the output switch β) are isomorphic. In this paper we: (1) derive some necessary conditions for the existence of balanced switching networks realizing various types of channel graphs, (2) solve completely the problem of the construction of 3‐stage balanced switching networks, and (3) give a recursive procedure to construct a class of balanced switching networks with more than three stages.
Minimal broadcast networks
Authors: Farley A. M.
Published: May 2007

Broadcast refers to the process of information dissemination in a communication network whereby a message, originated by one member, is transmitted to all members of the network. A minimal broadcast network is a communication network in which a message can be broadcast in minimum time regardless of originator. This paper describes several classes of minimal broadcast networks. An algorithm is presented which constructs minimal broadcast networks which have approximately the minimum number of lines possible.
The greedy travelling salesman's problem
Authors: Jenkyns T. A.
Published: May 2007

The Travelling Salesman's Problem is to find a Hamilton path (or circuit) which has minimum total weight W*, in a graph (or digraph) with a non‐negative weight on each edge. The Greedy Travelling Salesman's Problem is “How much larger than W* can the total weight G* of the solution obtained by the Greedy Algorithm be?”. Using the theory of independence systems, it is shown that G*‐W* may be as large as f(n,M,W*) where n is the number of vertices and M is the maximum edge‐weight. The function f is determined for the several variations of the Travelling Salesman's Problem and the bound is shown to be best possible in each case.
Network methods in models of production
Authors: Watson Donald
Published: May 2007

The author explores the ground common to the theories of electrical networks and economic networks by generalizing the notion of a Kirchhoff network of multiterminal elements to that of a Leontieff network of multiterminal elements. In this context the author introduces Le Chatelier's principle and proves a converse to it, derives a generalization of Tellegen's theorem, and discusses the inheritance by a composite element of the properties of its constituent elements. Two types of maximizing firms are then treated as multiterminal elements; the preceding theory is applied to them and to composite firms constructed from them.
The cyclic method of solving the transshipment problem with an additional linear constraint
Authors: Masch Victor V.
Published: May 2007

The “cyclic” method proposed in this paper provides a more efficient computational scheme than currently known adaptations of the simplex method for solving the transshipment problem with an additional linear constraint. Computer codes for the pure network problem can be easily altered to accommodate the cyclic method. Even more important, the cyclic method produces integral solutions at all iterations (except, possibly, the last one); this property may prove valuable in integer programming.
The k best spanning arborescences of a network
Authors: Camerini P. M. , Fratta L. , Maffioli F.
Published: May 2007

An efficient algorithm is presented for finding, in order, K best spanning arborescences in a given network with n vertices and m edges. The time is O(Km log n), and space is O(K + m).
An algorithm for finding a short closed spanning walk in a graph
Authors: Takamizawa K. , Nishizeki T. , Saito N.
Published: May 2007

A Hamiltonian walk of a graph is a closed spanning walk of minimum length. In this paper we generalize a Dirac type sufficient condition ensuring the existence of a Hamiltonian cycle to one ensuring the existence of a closed spanning walk of length less than a specified value. Furthermore, we present an O (p2 log p) algorithm for finding such a closed spanning walk in a graph with p vertices satisfying our condition.
Monotone sequences of graphical invariants
Authors: Harary Frank , Kabell Jerald A.
Published: May 2007

We investigate the extent to which certain graphical parameters can vary in successive point‐deleted subgraphs. In particular we identify one group of invariants which can be made to conform to an arbitrary monotone nondecreasing sequence and another group to a given nonincreasing sequence. Curiously, the two sets are not disjoint, as the line connectivity is in both. Finally we determine the most general sequences which can appear in this context.
Arc tolerances in shortest path and network flow problems
Authors: Shier D. R. , Witzgall Christoph
Published: May 2007

This paper studies one aspect of the “robustness” of optimal solutions to shortest path and, more generally, network flow problems. Specifically, we characterize the maximum increase and the maximum decrease in an arc's cost that can be tolerated without changing optimality of the current solution. Calculation of these quantities is quite simple for nonbasic arcs, and somewhat more involved for basic arcs. When such tolerances are to be determined simultaneously for all arcs in the network, considerable duplication of effort can be avoided through the use of specialized algorithms. Several algorithms for calculating all arc tolerances are presented, one of which is shown to have complexity order n2 for general networks with n nodes.
A dual algorithm for the constrained shortest path problem
Authors: Handler Gabriel Y. , Zang Israel
Published: May 2007

In this paper we develop a Lagrangian relaxation algorithm for the problem of finding a shortest path between two nodes in a network, subject to a knapsack‐type constraint. For example, we may wish to find a minimum cost route subject to a total time constraint in a multimode transportation network. Furthermore, the problem, which is shown to be at least as hard as NP‐complete problems, is generic to a class of problems that arise in the solution of integer linear programs and discrete state/stage deterministic dynamic programs. One approach to solving the problem is to utilize a kth shortest path algorithm, terminating with the first path that satisfies the constraint. This approach is impractical when the terminal value of k is large. Using Lagrangian relaxation we propose a method that is designed to reduce this value of k. Computational results indicate orders of magnitude savings when the approach is applied to large networks.
A cut approach to a class of quadratic integer programming problems
Authors: Picard Jean‐Claude , Ratliff H. Donald
Published: May 2007

This paper presents an algorithm for solving a class of quadratic integer programming problems. These problems include discrete versions of the quadratic placement problem and the squared Euclidean distance problem. The algorithm solves a sequence of at most Σ (ui ‐ li) minimum cut problems, or equivalently maximum flow problems, on a graph with n + 2 vertices where n is the number of variables in the problem, ui and li are upper and lower bounds, respectively, on the ith variable.
Covering and packing in graphs IV: Linear arboricity
Authors: Akiyama Jin , Exoo Geoffrey , Harary Frank
Published: May 2007

The linear arboricity of a graph is the minimum number of linear forests into which its lines can be decomposed. We find that the linear arboricity of every 4‐regular graph is 3. This result enables us to obtain bounds for the linear arboricity of any graph in terms of its maximum degree.
The design and analysis of heuristics
Authors: Ball Michael , Magazine Michael
Published: May 2007

This discussion session was concerned with the analysis of heuristics and the design of more effective heuristics. Initially, the group generated a list of evaluation criteria and discussed the strengths and weaknesses of each criterion. Next a classification of heuristic approaches was devised. Finally, the group compiled a list of promising research directions.
Networks immune to isolated failures
Authors: Farley Arthur M.
Published: May 2007

The notion of isolated failure immune (IFI) networks is introduced. A network is an IFI network if and only if all message transfers between operating sites can be completed as long as all site and line failures are isolated. Failures occurring at any time are isolated if they are pairwise isolated. A pair of site failures is isolated if the down sites are not neighbors. A pair of line failures is isolated if the lines are not incident to a common site. A site and a line failure are isolated if the down line is not incident to a neighbor of the down site. We show that 2‐trees are minimum IFI networks. An algorithm is described which adds lines to an arbitrary tree network to produce an IFI network (a 2‐tree). The algorithm also determines routing tables which allow a simple calling protocol to complete all message transfers between operative sites under isolated failures. Specializations and generalizations of our notion of IFI networks are discussed and issues for future research are proposed.
On the worst‐case performance of some algorithms for the asymmetric traveling salesman problem
Authors: Frieze A. M. , Galbiati G. , Maffioli F.
Published: May 2007

We consider the asymmetric traveling salesman problem for which the triangular inequality is satisfied. For various heuristics we construct examples to show that the worst‐case ratio of length of tour found to minimum length tour is (n) for n city problems. We also provide a new O([log2n]) heuristic.
Counting formulas for tree growth plans
Authors: Rowe Harrison E. , Mammel Wanda L.
Published: May 2007

We present counting formulas for the number of different ways to grow a given rooted tree, over a specified number of intervals. We call these growth plans, or simply plans. This problem arises, for example, in analog toll‐connect networks in which it is desired to introduce digital technology to serve increasing circuit requirements, in the cheapest way. Each circuit in such a network extends from a particular node called the toll center to one of the other nodes. The toll center corresponds to the root, and the portion of the network containing digital equipment corresponds to the rooted subtree whose growth we study. Even for networks of modest size and few growth intervals, the number of plans is too large to permit finding the cheapest by an exhaustive search. We observe that plans differing only in their growth pattern in the neighborhood of some particular node have cost differences that depend principally on their local growth patterns. It is therefore often possible to eliminate at a single stroke a large class of plans having a specified local growth plan at a particular node. By repetition, the number of remaining plans that must have their individual total costs computed can often be reduced to a number sufficiently small for an exhaustive search. We describe two types of local growth behavior appropriate for eliminating classes of plans in this network problem, and give corresponding counting formulas for the number of tree growth plans under these restrictions. A generalized counting formula with arbitrary local restrictions at each node is presented; this general formula contains the prior results as special cases. Finally, an example illustrates the great reduction in number of plans that can sometimes be obtained.
Locating mobile servers on a network with markovian properties
Authors: Berman Oded , Odoni Amedeo R.
Published: May 2007

The median problem has been generalized to the case in which facilities (“servers”) can be moved, at a cost, on the network in response to changes in the state of the network. Such changes are brought about by changes in travel times on the links of the network due to the occurrence of probabilistic events. For the case examined here, transitions among states of the network are assumed to be Markovian. The problem is examined for an objective which is a weighted function of demand travel times and of server relocation costs. It is shown that when these latter costs are a concave function of the time to travel from the current server location to the new server location, an optimal set of server locations exists solely on the nodes of the network. The location‐relocation problem can be formulated as an integer programming problem. The problem of locating a single server on a network which is a tree is shown to have a simple solution. A heuristic algorithm for the single server on a general network is also described. The paper develops simple bounds for the general multifacility, multistate problem and concludes with the description of a relaxed version of this model and with a discussion of the model's applicability.
On reliability in stochastic graphs
Authors: Frank Ove , Gaul Wolfgang
Published: May 2007

A complete graph has randomly failing nodes and edges. All failures are independent, and there is a common node reliability and a common edge reliability. Generalizing an approach developed by Gilbert for reliable nodes and unreliable edges, we find formulas for various kinds of connectedness probabilities. Bounds and approximations to the probabilities are given.
Networks immune to isolated line failures
Authors: Farley Arthur M. , Proskurowski Andrzej
Published: May 2007

A network is immune to a set of failures if all message transfers between operative sites can be completed in the presence of such failures. A set of line failures is isolated if no two failing lines are incident to the same site. Several classes of isolated line failure immune (ILFI) networks are defined, including a class with fewest lines for a given number of sites. An algorithm is presented which turns an arbitrary tree into one of these minimum ILFI networks and computes routing tables for the new network.
On a measure of communication network vulnerability
Authors: Exoo Geoffrey
Published: May 2007

A measure of communication network vulnerability was studied in a recent article by Boesch, Harary, and Kabell. The persistence (line persistence) is the minimum number of points (lines) whose removal from a graph increases its diameter. Their approach differed from earlier work on this topic in that they examined the analogs of Menger's theorem for these invariants. A result of Lovász, Neumann‐Lara, and Plummer is used to prove modified versions of their theorems (the original proofs are incorrect). Some related problems are also solved, including one posed by Hartman and Rubin.
Routing past unions of disjoint linear barriers
Authors: Chein Orin , Steinberg Leon
Published: May 2007

Given a disjoint planar set, {Li, = PiQi, i = 1,…, n}, of line segments called barriers, we consider the question of finding a path Γ of minimal length which connects two given points A and B and which does not “cut” any of the barriers. In Section III we show that such a minimal path exists and that it is polygonal with its bend points lying in W = {Pi, Qi: i = 1,…, n}. The problem is thus reduced to finding the shortest path between two points A and B in an approximate network with vertex set V = W ∪ {A, B}. The latter can be solved by a network routing algorithm such as Dantzig's. Section IV presents Algorithms for reducing the size of the network.
Finding a manhattan path and related problems
Authors: Lipski Witold
Published: May 2007

Let S be a set of n horizontal and vertical segments on the plane, and let s, t ∈ S. A Manhattan path (of length k) from s to t is an alternating sequence of horizontal and vertical segments s = r0, r1,…,rk = t where ri intersects ri+1, 0 ≤ i < k. An from all s ∈ S to t. Also given is a method to determine a maximum set of crossings (intersections of segments) with no two on the same segment, as well as a maximum set of nonintersecting segments, both in O(n3/2 log2 log2 n) time. The latter algorithm is applied to decomposing, in O(n3/2 log2 n) time, a hole‐free union of n rectangles with sides parallel to the coordinate axes into the minimal number of disjoint rectangles. All the algorithms require O(n log n) space, and for all of them the factor log2 n can be improved to log n log log n, at the cost of some complication of the basic data structure used.
An analysis of alternative strategies for implementing matching algorithms
Authors: Ball Michael O. , Derigs Ulrich
Published: May 2007

In this paper we explore implementation issues related to the solution of the weighted matching problem defined on an undirected graph G = (V, E). We present algorithms based on the two different linear characterizations of the feasible solutions to the matching problem. Furthermore, we present two specialized implementations, one with an O (|V|3) time bound and one with an O(|V‖E| log |V|) time bound. Both of these implementations have storage requirements that are linear in |V| and |E|. We initially develop these algorithms as special implementations of the well‐known primaldual (blossom) algorithm and then show how the updates they perform have an interesting interpretation when the algorithms are viewed as methods that successively find shortest augmenting paths. Finally, we show that postoptimality analysis can be performed very efficiently within this setting.
Graphs with the smallest number of minimum cut sets
Authors: Smith Derek
Published: May 2007

The number of vertex cut sets of size k in a graph of connectivity k has been used as a measure of network reliability. Let G be a regular graph with N vertices, valency k, connectivity k, and with the minimum number of vertex cut sets with k vertices. The problem of constructing such a graph G for each pair (N, k) is known to be difficult. We show how to construct infinite families of such graphs in various cases. These cases are spread through the range 3/8 ≤ k/N <1. We also deal with cases in which k is small and cases with N ‐ k small.
a generalized network flow model with application to power supply‐demand problems
Authors: Liu Chen‐Ching , Wu Felix F.
Published: May 2007

The conventional network flow model is generalized by replacing the capacity constraints on the flow of each arc by a constraint that the set of flows lies in a compact set; the resulting model is called the compact flow network model. A necessary condition for the maximal compact flow is presented. The max‐flow‐min‐cut theorem is generalized to compact flow networks. The condition that is required for the maximal flow to be equal to the minimal cut is examined. The max‐flow‐min‐cut theorem is used to derive a necessary and sufficient condition for feasibility of the multiterminal supply‐demand problem based on the compact flow model. As an application, the electric power supply‐demand problem is discussed from the compact flow point of view.
The amount of overtaking in a network of queues
Authors: Whitt Ward
Published: May 2007

Customer B overtakes customer A in a queueing system if A arrives before B but B departs first. To understand the phenomenon of overtaking in a network of queues and its impact on sojourn times, it is important to develop concepts of the amount of overtaking. In this paper, two stochastic measures of the amount overtaking are defined: the random number of customers overtaken by an arbitrary customer and the random permutation of the original order of n customers upon departure. Describing these measures, however, often presents rather difficult combinatorial and probabilistic problems. In this paper, we make several conjectures about the amount of overtaking in open Jackson networks and its impact on sojourn times. Then we describe the amount of overtaking in several smaller networks, for example, a single node with the first‐come first‐served discipline and instantaneous Bernoulli feedback.
Heuristics for finding a maximum number of disjoint bounded paths
Authors: Ronen D. , Perl Y.
Published: May 2007

We consider the following problem: Given an integer k and a network G with two distinct vertices s and t, find a maximum number of vertex disjoint paths from s to t of length bounded by k. In a recent work [9] it was shown that for length greater than four this problem is NP‐hard. In this paper we present a polynomial heuristic algorithm for the problem for general length. The algorithm is proved to give optimal solution for length less than five. Experiments show very good results for the algorithm.
Steiner trees, connected domination and strongly chordal graphs
Authors: White Kevin , Farber Martin , Pulleyblank William
Published: May 2007

We consider Steiner tree problems and connected dominating set problems for several classes of graphs. We give a polynomial algorithm and a min‐max theorem for the cardinality Steiner problem in strongly chordal graphs and a polynomial algorithm for the weighted connected dominating set problem in series‐parallel graphs. We establish simple direct transformations between Steiner problems and connected domination problems for several classes of graphs and establish related NP‐completeness results.
A factoring algorithm using polygon‐to‐chain reductions for computing K‐terminal network reliability
Authors: Wood R. Kevin
Published: May 2007

Let G = (V,E) be an undirected graph whose edges may fail, and let Gk denote G with a set k ⊆ V specified. Edge failures are assumed to be statistically independent and to have known probabilities. The k‐terminal reliability of Gk, denoted R(Gk), is the probability that all vertices in k are connected by working edges. Computing k‐terminal reliability is an NP‐hard problem not known to be in NP. A factoring algorithm for computing network reliability recursively applies the formula R(Gk) = PiR(Gk′*ei + qiR(Gk − ei)), where Gk′*ei is Gk with edge ei contracted, Gk − ei is Gk with ei deleted and pi = 1 − qi is the reliability of edge ei. Various reliability‐preserving reductions may be performed after each factoring operation in order to reduce computational complexity. The complexity of a slightly restricted factoring algorithm using standard reductions, along with newly developed polygon‐to‐chain reductions, will be bounded below by an invariant of G, the “minimum domination.” For 2 ≤ ∣K∣ ≤ 5 or ∣V∣ − 2 ≤ ∣K∣ ≤ ∣V∣, this bound is always achievable. The factoring algorithm with polygon‐to‐chain reductions will always perform as well as or better than an algorithm using only standard reductions, and for some networks, it will outperform the simpler algorithm by an exponential factor. This generalizes early results that were only valid for K = V. Removing the restriction on edge selection leaves results essentially unchanged in the upper range of ∣K∣, but minimum domination becomes only a tight upper bound for the lower range.
Combinatorial optimization problems in the analysis and design of probabilistic networks
Authors: Bauer D. , Boesch F. , Suffel C. , Tindell R.
Published: May 2007

This paper presents some results regarding the design of reliable networks. The problem under consideration involves networks which are undirected graphs having equal and independent edge failure probabilities. The index of reliability is the probability that the network fails (becomes disconnected). For “small” edge failure probabilities and given p and q there exists a class of p vertex, q edge graphs with the property that any graph in the class has a smaller probability of disconnection than any graph outside of the class. We solve the problem of synthesizing graphs in this class.
The minimum augmentation of a directed tree to a k‐edge‐connected directed graph
Authors: Kajitani Yoji , Ueno Shuichi
Published: May 2007

For a directed graph G, let d+(ν) and d (ν) be the outdegree and indegree of vertex ν, respectively. Given a positive integer k, the outdeficiency and indeficiency are defined by δ (ν) = max (k − d+ (ν), 0) and δ (ν) = max(k − d− (ν), 0), respectively. It is evident that in augmenting G to a k‐edge‐connected directed graph, at least δk(G) = max(Σδ (ν), Σδ (ν)) edges are necessary. This paper proves the theorem that if G is a directed tree (directed graph whose underlying graph is a tree) this number of edges is enough. The proof is made by presenting a construction procedure of polynomial‐order complexity.
Shortest paths in networks with exponentially distributed arc lengths
Authors: Kulkarni V. G.
Published: May 2007

This paper develops methods for the exact computation of the distribution of the length of the shortest path from a given source node s to a given sink node t in a directed network in which the arc lengths are independent and exponentially distributed random variables. A continuous time Markov chain with a single absorbing state is constructed from the original network such that the time until absorption into this absorbing state starting from the initial state is equal to the length of the shortest path in the original network. It is shown that the state space of this Markov chain is the set of all minimal (s, t) cuts in the network and that its generator matrix is upper triangular. Algorithms are described for computing the distribution and moments of the length of the shortest path based on this Markov chain representation. Algorithms are also developed for computing the probability that a given (s, t) path is the shortest path in the network and for computing the conditional distribution of the length of a path given that it is the shortest (s, t) path in the network. All algorithms are numerically stable and are illustrated by several numerical examples.
Linear arboricity of digraphs
Authors: Nakayama A. , Peroche B.
Published: May 2007

A linear diforest is a digraph whose connected components are paths. We define the linear arboricity of a digraph, denoted la(G), as the minimum number of linear diforests which partition the arcs of G. In this paper, we prove that the determination of la(G) is NP‐complete. We prove also that the problem becomes polynomial for acyclic digraphs. Finally, we give the value of la(G) for several families of digraphs, in particular 2‐regular digraphs.
An efficient implementation of the “partan” variant of the linear approximation method for the network equilibrium problem
Authors: Florian Michael , Guálat Jacques , Spiess Heinz
Published: May 2007

The PARTAN variant of the linear approximation method is adapted for solving the network equilibrium problem. A simple and efficient algorithm is stated. Its properties are analyzed by using algebraic and geometric approaches. Its computational efficiency on small and large scale problems is compared to that of the linear approximation method.
Some generalizations of the steiner problem in graphs
Authors: Duin C. W. , Volgenant A.
Published: May 2007

The Steiner Problem in Graphs (SP) is the problem of finding a set of edges with minimum total weight which connects a given subset of nodes in an edge‐weighted (undirected) graph. In the more general Node‐weighted Steiner Problem (NSP) also node weights are considered. A restricted minimum spanning tree model is adjusted for the NSP as well as for the Steiner Forest Problem, a newly introduced generalization. The NSP is related to the Directed Steiner Problem. Reduction tests for the SP, reducing the size of the problem graph, are adapted for these generalizations and some new tests are developed.
Generalizations of broadcasting and gossiping
Authors: Richards Dana , Liestman Arthur L.
Published: May 2007

Three generalizations of broadcasting and gossiping are considered: conference broadcasting in which broadcasting is done by conference calls, partial gossiping in which every gossip must learn at least k pieces of information, and set to set gossiping in which one subset of the members must learn all of the messages of another subset of the members.
Computational complexity of PERT problems
Authors: Hagstrom Jane N.
Published: May 2007

Computational complexity results for two PERT problems are presented. A project is specified by precedence relations among tasks. Task durations are independent random variables with discrete, finite ranges. The following results are obtained: (1) computing a value of the cumulative distribution function of project duration is #P‐complete, (2) computing the mean of the distribution is at least as hard, and (3) neither of the problems in (1) and (2) can be computed in time polynomial in the number of points in the range of the project duration unless P = NP.
Stochastic shortest paths with recourse
Authors: Andreatta Giovanni , Romeo Luciano
Published: May 2007

This paper considers Stochastic Shortest Path (SSP) problems in probabilistic networks. A variety of approaches have already been proposed in the literature. However, unlike in the deterministic case, they are related to distinct models, interpretations and applications. We have chosen to look at the case where detours from the original path must be taken whenever the “first‐choice” arc fails. The main results obtained include the proof of some counterintuitive facts (e.g., the SSP may contain a cycle), the proof of the validity of applying stochastic programming to this problem and the proof that the computational complexity of a particular SSP problem is polynomial.
Antiapoptotic effect of found in inflammatory zone (FIZZ)1 on mouse lung fibroblasts
Authors: Chung MJ , Liu T , Ullenbruch M , Phan SH
Published: May 2007

Myofibroblasts play an essential role in the abnormal deposition of extracellular matrix in pulmonary fibrosis. The presence or prolonged survival of these cells may be a key factor in the pathogenesis of progressive pulmonary fibrosis. Found in inflammatory zone (FIZZ)1 can induce myofibroblast differentiation and has an antiapoptotic effect on embryonic lung explant cultures. In this study, we investigated whether FIZZ1 also has an antiapoptotic effect on mouse lung fibroblasts (MLFs). Cells were treated with FIZZ1 for 24 h and then apoptosis was induced by TNFα in the presence of cycloheximide (CHX). FIZZ1 exhibited an antiapoptotic effect in MLFs, as assessed by flow cytometric analysis and TUNEL staining. Moreover, the cell number was higher in the FIZZ1‐treated group relative to the non‐treated control group after treatment with TNFα and CHX. FIZZ1 treatment also inhibited the apoptotic agent‐induced activities of caspase‐3 and caspase‐8. Examination of potential signalling pathways revealed that FIZZ1 induced rapid phosphorylation of ERK‐1/2, while PD98059, a MEK/ERK inhibitor, markedly induced activation of caspase‐3. This anti‐apoptotic effect of FIZZ1 was associated with induction of myofibroblast differentiation in response to FIZZ1 stimulation. Taken together, these findings suggest that FIZZ1 is involved in pulmonary fibrosis through both induction of myofibroblast differentiation and increased or prolonged survival of myofibroblasts. This effect of FIZZ1 was mediated by inhibition of caspase‐3 and ‐8, with involvement of the ERK pathway. Copyright © 2007 Pathological Society of Great Britain and Ireland. Published by John Wiley & Sons, Ltd.
Synthesis and characterization of poly (hydroxyether ketone) and its copolymers
Authors: Yang Xingtian , Zheng Sixun
Published: May 2007

A novel semi‐crystalline polyhydroxyether, poly(hydroxyether ketone) (PHEK), was synthesized via the direct polycondensation between 4,4‐dihydroxybenzophenone and epichlorohydrin. By means of Fourier transform infrared and NMR spectroscopy and gel permeation chromatography (GPC), the structure of PHEK was characterized. Differential scanning calorimetry (DSC) and wide‐angle X‐ray diffraction (WAXRD) show that PHEK is a semi‐crystalline polymer with a high rate of crystallization. The polymer possesses a glass transition temperature of 109 °C and a melting temperature of 239 °C. When 4,4′‐isopropylidenediphenol was used as a second bisphenol and was added to copolymerize with a stoichiometric amount of epichlorohydin, a series of polyhydroxyether copolymers were obtained. The copolymers with various compositions were characterized by means of NMR, GPC, WAXRD and DSC. It was found that the crystallinity of the copolymers dramatically decreased with increasing content of 4,4′‐isopropylidenediphenol. The glass transition temperatures of the copolymers are intermediate between those of PHEK and the poly(hydroxyether of bisphenol A) and decreased with increasing content of 4,4′‐isopropylidenediphenol. Copyright © 2007 Society of Chemical Industry
Automated serum peptide profiling using novel magnetic C18 beads off‐line coupled to MALDI‐TOF‐MS
Authors: Jimenez Connie R. , El Filali Zineb , Knol Jaco C. , Hoekman Klaas , Kruyt Frank A. E. , Giaccone Giuseppe , Smit August B. , Li Ka Wan
Published: May 2007

Serum peptide profiling by MS is an emerging approach for disease diagnosis and biomarker discovery. A magnetic bead‐based method for off‐line serum peptide capture coupled to MALDI‐TOF‐MS has been recently introduced. However, the reagents are not available to the general scientific community. Here, we developed a protocol for serum peptide capture using novel magnetic C18 beads, and automated the procedure on a high‐throughput magnetic particle processor. We investigated bead equilibration, peptide binding and peptide elution conditions. The method is evaluated in terms of peaks counts and reproducibility of ion intensities in control serum. Overall, the DynaBead‐RPC18‐based serum sample processing protocol reported here is reproducible, robust and allows for the detection of ˜200 peptides at m/z 800–4000 of serum that was allowed to clot for 1 h. The average intra‐experiment %CV of normalized ion intensities for crude serum and 0.5% TFA/0.15% n‐octyl glucoside‐treated serum, respectively, were 12% (range 2–38%) and 10% (3–21%) and the inter‐experiment %CVs were 24% (10–53%) and 31% (10–59%). Importantly, this method can be used for serum peptide profiling by anyone in possession of a MALDI‐TOF instrument. In conjunction with the KingFisher® 96, the whole serum peptide capture procedure is high‐throughput (˜20 min per isolation of 96 samples in parallel), thereby facilitating large‐scale disease profiling studies.
Stable non‐supersymmetric vacua at the bottom of cascading gauge theories
Authors: Argurio R. , Bertolini M. , Closset C. , Cremonesi S.
Published: May 2007

We consider a wide class of cascading gauge theories which usually lead to runaway behavior in the IR, and discuss possible deformations of the superpotential at the bottom of the cascade which stabilize the runaway direction and provide stable non‐supersymmetric vacua. The models we find may allow for a dual weakly coupled supergravity analysis of dynamical supersymmetric breaking.
Weyl‐invariant lightlike branes and soldering of black hole space‐times
Authors: Guendelman E.I. , Kaganovich A. , Nissimov E. , Pacheva S.
Published: May 2007

We consider self‐consistent coupling of the recently introduced new class of Weyl‐conformally invariant lightlike branes (WILL‐branes) to D = 4 Einstein‐Maxwell system plus a D = 4 three‐index antisymmetric tensor gauge field. We find static spherically‐symmetric solutions where the space‐time consists of two regions with different black‐hole‐type geometries and different values for a dynamically generated cosmological constant, separated by the WILL‐brane which “straddles” their common event horizon. Furthermore, the WILL‐brane produces a potential “well” around itself acting as a trap for test particles falling towards the horizon.
Microstates and near‐horizon D‐brane probes
Authors: Raeymaekers J.
Published: May 2007

In [1], Gaiotto, Strominger and Yin proposed a novel way of counting black hole microstates by counting the quantum mechanical ground states of probe branes placed in the near‐horizon black hole background. We discuss the generalization of this proposal to the case of two‐charge D0‐D4 ‘small’ black holes in type IIA. We also describe the construction of BPS D‐brane probes in the near‐horizon region of the 2‐charge D1‐D5 system in type IIB.
On meta‐stable SQCD with adjoint matter and gauge mediation
Authors: Amariti A. , Girardello L. , Mariotti A.
Published: May 2007

We briefly review our analysis of a model with non supersymmetric vacua in 𝒩 = 1 gauge theories with adjoint matter and no R‐symmetry. We show here that this model without any modification fits into a direct gauge mediation scenario and leads to massive gauginos.
Adding D7‐branes to the Polchinski‐Strassler gravity background
Authors: Apreda R. , Erdmenger J. , Lüst D. , Sieg C.
Published: May 2007

We motivate and summarize our analysis of hep‐th/0610276 in which we consider D7‐brane probe embeddings in the Polchinski‐Strassler background with 𝒩 = 2 supersymmetry. The corresponding dual gauge theory is given by the 𝒩 = 2* theory with fundamental matter. Based on a talk given by C. Sieg at the RTN Workshop 2006, Napoli.
Consistent de Sitter string vacua from Kähler stabilization and D‐term uplifting
Authors: Parameswaran S.L. , Westphal A.
Published: May 2007

In this note, we review our construction of de Sitter vacua in type IIB flux compactifications, in which moduli stabilization and D‐term uplifting can be combined consistently with the supergravity constraints. Here, the closed string fluxes fix the dilaton and the complex structure moduli while perturbative quantum corrections to the Kähler potential stabilize the volume Kähler modulus in an AdS4‐vacuum. Then, magnetized D7‐branes provide consistent supersymmetric D‐term uplifting towards dS4. Based on hep‐th/0602253.
Spinor formulism, unitarity cut and reduction
Authors: Feng Bo
Published: May 2007

In this talk we present a new method to do reduction for one‐loop amplitudes using unitarity cuts. Our method uses the tree‐level amplitudes as input so it is a very efficient method.