bluuebunny/crossref_metadata_2025 huggingface dataset:
A two‐stage network with dual partial concentrators
Authors: Hwang F. K. , Richards G. W.
Published: May 2007

A two‐stage rearrangeable broadcast network (called an ordinary network here) that has been studied recently has a partial concentrator on the input side. We extend this study to a network with two partial concentrators: one on the input side and the other on the output side. We first study the network as a connection network and derive conditions for its rearrangeability. We show that the conditions are tight in some cases. We then show that a particular construction that meets the rearrangeability conditions actually yields a broadcast network. © 1993 John Wiley & Sons, Inc.
Doubly chordal graphs, steiner trees, and connected domination
Authors: Moscarini M.
Published: May 2007

A new class of chordal graphs, containing the class of strongly chordal graphs, is introduced. It is shown that these graphs, called doubly chordal graphs, are related to acyclic hypergraphs and are recognizable in polynomial time. Furthermore, after proving that the Steiner tree and the connected domination problems are polynomially solvable for doubly chordal graphs, it is shown that both problems are NP‐hard for a class of chordal graphs (called Helly chordal graphs) containing the class of doubly chordal graphs. © 1993 John Wiley & Sons, Inc.
Local broadcasting in a tree under minisum criterion
Authors: Koh Jae‐Moon , Tcha Dong‐Wan
Published: May 2007

This paper is concerned with information dissemination in a tree. It is assumed that a vertex can either transmit or receive a message and an informed vertex can transmit it to only one of its neighbors at a time. Under a minisum criterion, a necessary and sufficient condition for an optimal call sequence at each vertex is established. Based on this, an O(N log N) algorithm is designed to find optimal call sequences at all vertices and to determine the broadcast center of a tree—the set of all vertices from which minisum broadcasting can be accomplished. © 1993 John Wiley & Sons, Inc.
Shortest paths, single origin‐destination network design, and associated polyhedra
Authors: Magnanti Thomas L. , Mirchandani Prakash
Published: May 2007

We study a specialized version of network design problems that arise in telecommunications, transportation, and other industries. The problem, a generalization of the shortest path problem, is defined on an undirected network consisting of a set of arcs on which we can install (load), at a cost, a choice of up to three types of capacitated facilities. Our objective is to determine the configuration of facilities to load on each arc that will satisfy the demand of a single commodity at the lowest possible cost. Our results (i) demonstrate that the single‐facility loading problem and certain “common break‐even point” versions of the two‐facility and three‐facility loading problems are polynomially solvable as a shortest path problem; (ii) show that versions of the two‐facility loading problem are strongly NP‐hard, but that a shortest path solution provides an asymptotically “good” heuristic; and (iii) characterize the optimal solution (i.e., specify a linear programming formulation with integer solutions) of the common break‐even point versions of the two‐facility and three‐facility loading problems. In this development, we introduce two new families of facets, give geometric interpretations of our results, and demonstrate the usefulness of partitioning the space of the problem parameters to establish polyhedral integrality properties. Generalizations of our results apply to (i) multicommodity applications and (ii) situations with more than three facilities. © 1993 by John Wiley & Sons, Inc.
Edge fault tolerance in graphs
Authors: Harary Frank , Hayes John P.
Published: May 2007

A graph or multigraph G* is k‐edge fault‐tolerant with respect to a graph G, denoted k‐EFT(G), if every graph obtained by removing any k edges from G* contains G. We observe that for k sufficiently large a k‐EFT(G) graph must be a multigraph, and we present some basic conditions that such multigraphs must meet. We then study the problem of constructing k‐EFT(G) graphs that are optimal in that they contain the minimum number of edges among all k‐EFT(G) graphs. Families of optimal k‐EFT(G) graphs, where G is the n‐node path or cycle, are presented for all k and n. We also give an optimal 1‐EFT design for the n‐dimensional hypercube. © 1993 by John Wiley & Sons, Inc.
Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry
Authors: Akl S. G. , Qiu K. , Stojmenović I.
Published: May 2007

The star and pancake networks were recently proposed as attractive alternatives to the hypercube topology for interconnecting processors in a parallel computer. However, few parallel algorithms are known for these networks. In this paper, we present several data communication schemes and basic algorithms for these two networks. These algorithms are then used to develop parallel solutions to various computational geometric problems on both networks. Computational geometry is just one area where the algorithms proposed here can be applied. Indeed, we believe that these algorithms are interesting and important in their own right and are fundamental to the design of solutions on the star and pancake networks to a host of other problems. © 1993 by John Wiley & Sons, Inc.
On the adjacency properties of paley graphs
Authors: Ananchuen W. , Caccetta L.
Published: May 2007

In the application of graph theory to problems arising in network design, the requirements of the network can be expressed in terms of restrictions on the values of certain graph parameters such as connectivity, edge‐connectivity, diameter, and independence number. In this paper, we focus on networks whose requirements translate into adjacency restrictions on the graph representing the network. More specifically, a graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices there are at least k other vertices, each of which is adjacent to the first m vertices but not adjacent to any of the latter n vertices. The problem that arises is that of characterizing graphs having property P(m,n,k). In this paper, we present properties of graphs satisfying the adjacency property. In particular, for q  1(mod 4), a prime power, the Paley graph Gq of order q is the graph whose vertices are elements of the finite field 𝔽q; two vertices are adjacent if and only if their difference is a quadratic residue. For any m, n, and k, we show that all sufficiently large Paley graphs satisfy P(m,n,k). © 1993 by John Wiley & Sons, Inc.
Some minimum gossip graphs
Authors: Labahn Roger
Published: May 2007

What is the minimum number of edges that a graph on n vertices must have to allow gossiping by bidirectional telephone calls within ⌈log2 n⌉ rounds? Besides general estimates, this question is finally answered for integers of the form n = 2p − 2 (p ≥ 3) or n = 2p − 4 (p ≥ 6), and for n = 10, 12. Moreover, for n = 14, we prove the uniqueness of such a graph. © 1993 by John Wiley & Sons, Inc.
Communication structures in fault‐tolerant distributed systems
Authors: Pradhan Dhiraj K. , Meyer Fred J.
Published: May 2007

The impact of communication structures on the robustness and performance of distributed computing systems is discussed. Communication structures are categorized as (1) point‐to‐point, (2) bus, and (3) multistage switching. The most significant networks that have been proposed are discussed. Networks are compared with respect to (1) connectivity, (2) diameter, (3) average distance, (4) diameter in the presence of faults, (5) extensibility (ease of adding or deleting processors), and (6) ease of routing in the presence of faults. Some attempts directed at achieving near optimality for each of these six factors are discussed. A strategy for designing good networks with respect to all of these factors is suggested. Attempts to predict the real‐time robustness of systems are reviewed and commented on and the power and consistency of metrics associated with such attempts are discussed. The impact of communication structures is discussed with respect to fundamental fault‐tolerant objectives, such as diagnosis and disconnection of faulty units and establishment of a logical link between units not connected by a physical link. Current trends and suggested trends in communication network research are commented on. ©1993 by John Wiley & Sons, Inc.
Off‐line permutation routing on circuit‐switched fixed‐routing networks
Authors: Youssef Abdou
Published: May 2007

Circuit‐switched fixed routing (CSFR) is an increasingly popular communication model wherein there is between every source—destination pair a single path that is system‐determined by a fixed‐routing rule. This paper studies the new problem of off‐line permutation scheduling on linear arrays, rings, hypercubes, and 2‐dimensional arrays, assuming the CSFR model. Optimal permutation scheduling involves finding a minimum number of subsets of nonconflicting source—destination paths. Every subset of paths can be established to run in one pass. In this paper, optimal permutation scheduling on linear arrays is shown to be linear, and on rings, NP‐complete. On hypercubes, the problem is NP‐complete. However, we will give an O(N log N) algorithm that routes any permutation in two passes if the model is relaxed to allow for two routing rules, namely, the so‐called e‐cube rule and the e−1‐cube rule. This complexity is reduced to O(N) hypercube‐parallel time. Finally, an O(N log2 N) bipartite‐matching‐based algorithm will be designed to schedule any permutation on p × q meshes/tori in q passes. © 1993 by John Wiley & Sons, Inc.
A very short proof of a conjecture concerning set‐to‐set broadcasting
Authors: Li Qiao , Zhang Zhongliang , Xu Junming
Published: May 2007

We present a very short proof of a conjecture of Richards and Liestman concerning set‐to‐set broadcasting. © 1993 by John Wiley & Sons, Inc.
Most reliable double loop networks in survival reliability
Authors: Hu X. D. , Hwang F. K. , Li Wen‐Ch'Ing Winnie
Published: May 2007

Double loop networks have been intensively studied as interconnecting networks. However, the reliability analysis of such networks has hit a snag since the usual measure of reliability, the graph connectivity, is completely powerless as all double loops, if connected, are 2‐connected. Recently, Hwang and Li introduced a new analysis by partitioning cutsets into isolated and nonisolated ones and gave results on both types. Along the same line, we extent their results to the survival reliability model by showing that when each node fails independently with a very small probability, G(1, 1 + [n/2]) is the most reliable connected double loop network except when n = 3 and 9, in which case G(1, 2) is the most reliable. © 1993 by John Wiley & Sons, Inc.
Bounding procedures for multistage stochastic dynamic networks
Authors: Frantzeskakis Linos F. , Powell Warren B.
Published: May 2007

This paper presents new procedures for obtaining upper and lower bounds in the cost minimization of multistage dynamic networks with random link capacities and contrasts them to existing methods. These methods include adaptation of Jensen's inequality to the problem, Monte‐Carlo simulations and an analytical approximation procedure. The new bounding procedures involve a backward pass in the network coupled with a linear approximation at each stage. Some numerical results are presented for networks of substantial size. © 1993 by John Wiley & Sons, Inc.
Sensitivity analysis in stochastic flow networks using the Monte Carlo method
Authors: Alexopoulos Christos , Fishman George S.
Published: May 2007

Consider a flow network whose nodes do not restrict flow transmission and arcs have random, discrete, and independent capacities. Let s and t be a pair of selected nodes, let δ denote the value of a maximum s—t flow, and let Γ denote a set of s–t cuts. Also, let ℱ denote a set of independent joint capacity distributions with common state space. For fixed l < u, this paper develops methods for approximating the probability that l ≤ Δ < u and the probability that a cut in Γ is minimum given that l ≤ δ < u for each distribution in ℱ. Since these evaluations are NP‐hard problems, it shows how information obtained during an iterative procedure for computing the probability that l ≤ δ < u can be used for designing an efficient Monte Carlo sampling plan that performs sampling at few capacity distributions and uses sampling data to estimate the probabilities of interest at each distribution in ℱ. The set of sampling distributions is chosen by solving an uncapacitated facility location problem. The paper also describes techniques for computing confidence intervals and includes an algorithm for implementing the sampling experiment. An example illustrates the efficiency of the proposed method. This method is applicable to the computation of performance measures for networks whose elements have discrete random weights (lengths, gains, etc.) for a set of joint weight distributions with common state space. © 1993 by John Wiley & Sons, Inc.
Some graph‐theoretical models for scheduling in automated production systems
Authors: de Werra D. , Solot Ph.
Published: May 2007

Variations and extensions of the Open‐Shop Scheduling Problem are presented with an emphasis on models suitable for some automated production systems. Complexity results are given and polynomially solvable cases are described. © 1993 by John Wiley & Sons, Inc.
The dynamic predicate stashing copy problem
Authors: Sansó Brunilde , Soumis François
Published: May 2007

One important issue being addressed in the design of Distributed Computer Networks is how to increase the availability of time‐changing information even in the event of failures. Recently, a technique called “stashing” was proposed. Stashing a file signifies placing a copy of that file in several nodes of the network. In addition, a “predicate” has been defined as a consistency requirement for a particular file copy with respect to the original. We address the problem of minimizing the propagation cost of stashed copies subject to predicate restrictions imposed by the user. In the version of the problem that we tackle, the user may receive a copy with a predicate better than requested. We call this problem the Dynamic Predicate Stashing Copy Problem (DPSCP) and propose a formulation to solve it. Resolution approaches, numerical results, and properties of the problem are also discussed. © 1993 by John Wiley & Sons, Inc.
A simple and fast label correcting algorithm for shortest paths
Authors: Bertsekas Dimitri P.
Published: May 2007

We propose a new method for ordering the candidate nodes in label correcting methods for shortest path problems. The method tries to scan nodes with small labels as early as possible and may be viewed as a low‐overhead approximation to Dijkstra's algorithm. Compared with the D'Esopo–Pape algorithm, our method is equally simple but much faster. Our method can also be combined with the threshold algorithm, thereby considerably improving its practical performance. © 1993 by John Wiley & Sons, Inc.
Improving the location of minimax facilities through network modification
Authors: Berman Oded , Ingco Divinagracia I. , Odoni Amedeo
Published: May 2007

Consider a network on which one or more facilities are already located. We examine how the network can be modified most efficiently in order to improve the location of the facility when the measure of facility performance is the minimax objective. The types of possible network modifications fall into two categories: reductions in the length of existing arcs or additions of some new arcs that are not currently in the network. A set of reduction and addition problems is introduced for which exact or heuristic algorithms are presented. The principal objective of the paper is in defining and formulating the problems and not in testing the efficacy of the proposed solution methodologies. © 1994 by John Wiley & Sons, Inc.
Universal minimal total dominating functions in graphs
Authors: Cockayne E. J. , Mynhardt C. M. , Yu Bo
Published: May 2007

A total dominating function (TDF) of a graph G = (V, E) is a function f: V → [0, 1] such that for each ν ϵ V, ΣuϵN(v) f(u) ⩾ 1 [where N(v) denotes the open neighborhood of vertex v]. Integer‐valued TDFs are precisely characteristic functions of total dominating sets of G. Convex combinations of two TDFs are themselves TDFs but convex combinations of minimal TDFs (MTDFs) are not necessarily minimal. This paper is concerned with the existence of a universal MTDF in a graph, i.e., a MTDF g such that convex combinations of g and any other MTDF are themselves minimal. © 1994 by John Wiley & Sons, Inc.
Probabilistic analysis of an enhanced partitioning algorithm for the steiner tree problem in Rd
Authors: Kalpakis Konstantinos , Sherman Alan T.
Published: May 2007

The Geometric Steiner Minimum Tree problem (GSMT) is to connect at minimum cost n given points (called terminals) in d‐dimensional Euclidean space. We generalize a GSMT approximation partitioning algorithm by Komlós and Shing (KS) and analyze its performance under more relaxed conditions. These generalizations have practical applications for multilayer VLSI routing. Whereas KS assumed d = 2, our algorithm works for any dimension d ⩾ 2. Moreover, whereas their analysis assumed the rectilinear norm and a uniform distribution of input points, our analysis holds for any norm on Rd and whenever the terminals are any independent identically distributed random variables taking on values in any bounded subset of Rd. Both algorithms depend on a parameter t through which the user can trade off time for solution quality. We evaluate our algorithm in terms of its performance ratio–the ratio of the cost of the Steiner tree computed by the algorithm divided by the cost of a Steiner minimum tree. Applying a probability theorem on subadditive Euclidean functionals by Steele, we prove the following: Under the aforementioned distribution of inputs, the limit as n → ∞ of the supremum of the performance ratio of our algorithm is 1 + Ot−1/d(d‐1), almost surely. This result generalizes the corresponding 1 + O(t−1/2) bound proven by KS. Along the way, we prove a useful combinatorial lemma about d‐dimensional rectangle slicings. We prove that the worst‐case time and space complexity of our algorithm is θ(n lg (n/t) + TMST(v, v) + nTSMT(t)/t) and θ(SMST(v, v) + SSMT(t)), respectively, where v ⩽ n + 2d+1 (n/t) σ(t) is the number of vertices in the resulting Steiner tree. Here, TSMT(t) and SSMT(t) are the time and space required to solve exactly any GSMT problem of size less than t; TMST(n, m) and SMST(n, m) are the time and space required to find a minimum spanning tree of a graph with n nodes and m edges; and σ(t) is the maximum number of Steiner points for any Steiner minimum tree with t terminals. For example, for R2 and the rectilinear norm, the time is O(n lg(n/t) + n lg*n + nTSMT(t)/t) and the space is O(n lg *n + SSMT(t)). © 1994 by John Wiley & Sons, Inc.
A separation decomposition for orders
Authors: Kämpke Thomas
Published: May 2007

Several decomposition types of orders and related discrete structures have been investigated so far. In this paper, we present a decomposition for orders based on partial “ignoring” of the order. Structures that are in a certain sense “prime” turn out to be decomposable. The relation to other decomposition methods is analyzed. Bounds for activity networks and reliability functions are obtained. © 1994 by John Wiley & Sons, Inc.
Measures of vulnerability–the integrity family
Authors: Goddard Wayne
Published: May 2007

In this paper, a schema of graphical parameters is proposed. Based on the parameter integrity introduced by Barefoot, Entringer, and Swart, members Ψ(G) of this schema have the general form Ψ(G) = min {|S| + Ψ(G ‐ S) : S Ψ V (G)}, where Ψ(G) is another given graphical parameter. Examples include integrity, mean integrity, connectivity, and vertex cover number. General results and bounds for the schema are derived. Also, properties that characterize such parameters are considered. © 1994 by John Wiley & Sons, Inc.
Spanners in graphs of bounded degree
Authors: Cai Leizhen , Keil Mark
Published: May 2007

Given a graph G = (V, E), a subgraph S = (V, Es) is a t‐spanner of G if for every edge xy ϵ E the distance between x and y in S is at most t. Spanners have applications in communication networks, distributed systems, parallel computation, and many other areas. This paper is concerned with the complexity of finding a minimum size t‐spanner in a graph with bounded degree. A linear time algorithm is presented for finding a minimum‐size 2‐spanner in any graph whose maximum degree is at most four. The algorithm is based on a graph theoretical result concerning edge partition of a graph into a “triangle‐free component” and “triangular‐components.” On the other hand, it is shown that to determine whether a graph with maximum degree at most nine contains a t‐spanner with at most K edges (K is given) is NP‐complete for any fixed t ⩾ 2. © 1994 by John Wiley & Sons, Inc.
On reliability of graphs with node failures
Authors: Goldschmidt Olivier , Jaillet Patrick , Lasota Richard
Published: May 2007

We consider the reliability of graphs for which nodes fail independently of each other with a constant probability 1 ‐p. The reliability of a graph is defined to be the probability that the induced subgraph of surviving nodes is connected. A graph is said to be uniformly best when, for all choices ofp, it is most reliable in the class of graphs with the same number of nodes and same number of edges. In this paper, we first extend the existing known set of uniformly best graphs. Next, we show that most classes of sparse graphs do not contain a uniformly best graph. Finally, we introduce the important notions of locally best and asymptotically best graphs and illustrate these concepts with a detailed study of graphs having the same number of nodes and edges. © 1994 by John Wiley & Sons, Inc.
Compressing grids into small hypercubes
Authors: Miller Zevi , Sudborough I. H.
Published: May 2007

Let G be a graph, and denote by Q(G)/2t the hypercube of dimension ⌈log2|G|⌉ − t. Motivated by the problem of simulating large grids by small hypercubes, we construct maps f:G → Q(G)/2t, t ⩾ 1, when G is any 2‐ or 3‐dimensional grid, with a view to minimizing communication delay and optimizing distribution of G‐processors in Q(G)/2t, Let dilation(f) = max {dist(f(x), f(y)): xyε(G)}, where “dist” denotes distance in the image network Q(G)/2t, and let the load factor of f be the maximum value of >f−1(h)| over all vertices hε(G)/2t. Our main results are the following: (1) Let G be any 2‐dimensional grid. Then, for any t ⩾ 1, there is a map f :G → Q(G)/2t having dilation 1 and load factor at most 1 + 2t. (2) Given certain upper bounds on the “densities” |G|/|Q(G)/4| or |G|/|Q(G)/8| of G in Q(G)/4 or Q(G)/8, respectively, we get dilation 1 maps f:G → Q(G)/4 or f:G → Q(G)/8 with improved (i.e., smaller) load factor over that given in (1). (3) Let G be any 3‐dimensional grid. Then, there is a map f:G → Q(G)/2 of dilation at most 2 and load factor at most 3, and a map f:G → Q(G)/4 of dilation at most 3 and load factor at most 5.
Efficient algorithms for minimum range cut problems
Authors: Katoh Naoki , Iwano Kazuo
Published: May 2007

LetG = (V, E)be an undirected graph withnvertices andmedges such that a real‐valued weight, denoted byw(e), is associated with each edgee. This paper studies what we call the minimum range cut problem that asks to find a cut inGsuch that the range of all edge weights in the cut is minimum. Here, the range of a cutCis defined to be the maximum difference among weights of edges in the cut, i.e., maxeϵcw(e)‐ mineϵcw(e). This paper proposes anO(m + nlogn) algorithm for the minimum range cut problem. It is also shown that this running time is optimal. We also study two variants of this problem. One is the minimum range target cut problem. Given a prespecified value called a target, this problem asks to find a cut with minimum range among all cuts such that the target value is between the minimum and maximum of weights of edges in the cut. The second is the minimum ranges – tcut problem that asks to find ans – tcut with minimum range. This paper proposesO(m + nlogn) algorithms for these problems. For the second problem, we show that anancestor treeofO(n)space recently developed by Cheng and Hu effectively represents all pairs minimum range cuts, which can be constructed inO(n2)time, and enables us to answer any minimum ranges – tcut query inO(1)time [resp., inO(n)time] if we want to obtain only the range value of the cut (resp., the bipartition of vertices induced by the cut). © 1994 by John Wiley & Sons, Inc.
An algorithm for generating minimum cost network flow problems with specific structure and known optimal solutions
Authors: Arthur Jeffrey L. , Frendewey James O.
Published: May 2007

A new algorithm for generating structured, minimum cost network flow problems (transshipment, transportation, assignment, and shortest path) with known optimal solutions is described. The procedure is based on developing problems around an optimal basis so that the characteristics of solutions can be controlled. Computational tests show that the problems generated are as difficult to solve as are those produced by the commonly used generator NETGEN, while allowing the user a much greater degree of control over the resulting problems. © 1994 by John Wiley & Sons, Inc.
Monte Carlo and Markov Chain techniques for network reliability and sampling
Authors: Buchsbaum Adam L. , Mihail Milena
Published: May 2007

We examine a heuristic to approximate various reliability‐related parameters of communications networks under link failures. The heuristic is based on Monte Carlo and Markov chain simulation techniques. (These techniques have emerged in recent years in theoretical computer science in the context of obtaining efficient approximations forNP‐hard combinatorial optimization problems.) We present the ideas of these Monte Carlo and Markov chain techniques in terms of a specific reliability measure. The general method could be applicable to other reliability measures, just as it has been applied to other combinatorial problems. We present initial experimental results that suggest our approach is typically efficient in the computational complexity sense (running in time polynomial the size of the input); furthermore, our results suggest practical applicability for medium‐size networks and single‐edge parameters. As an example, we present the results of our experiments on a network that was posed for analysis by Applied Research at Bellcore: We estimated all single‐edge parameters on a single DEC‐5000 in less than 4 hours. The software that supported our experiments involves approximately 3000 lines of C code and is easy to adapt to other applications.
A forbidden minor characterization and reliability of a class of partial 4‐trees
Authors: Lingner Gerard T. , Politof Themistocles , Satyanarayana A.
Published: May 2007

This paper characterizes a class 𝒢 of partial 4‐trees in terms of a set of seven forbidden minors. The class 𝒢 contains several known classes of graphs, including both Δ ‐ Y and Y ‐ Δ graphs. A set of six graph reduction operations is defined, and it is shown that a graph G ∈ 𝒢 iff G can be reduced to an edgeless graph by a finite sequence of these operations. The all‐terminal reliability R(G) of a graph G is the probability that G is connected. The characterization of 𝒢 is used to develop an O(n log n) algorithm to compute R(G) for all n‐point graphs in 𝒢. The running time is O(n) for planar graphs in 𝒢.
Consecutive cuts and paths, and bounds onk‐terminal reliability
Authors: Strayer Heidi J. , Colbourn Charles J.
Published: May 2007

Shanthikumar developed an upper bound for two‐terminal reliability based on consecutives – tcutsets. Subsequently, Shier generalized this strategy to obtain upper bounds from cutsets, and lower bounds from pathsets, when the cutsets or pathsets form a semilattice structure. We examine a restricted case of Shier's method that yields ak‐terminal lower bound based on consecutive pathsets. Our approach employs a common reduction of consecutive cut and path bounds to the computation of the two‐terminal reliability of an interval graph with imperfect vertices. Computational results are given to support the observation that the consecutive paths lower bound is competitive with the best efficiently computable bounds that are currently available. We then apply the consecutive path bound to reduce, in some cases dramatically, the number of states generated in a most probable state bounding method.
An adaptive discretization algorithm for a class of continuous network programs
Authors: Philpott Andrew B. , Craddock Mark
Published: May 2007

An algorithm is derived for a class of continuous‐time minimum‐cost network flow problems. The algorithm is based on some recent results in the theory of separated continuous linear programs and works with a sequence of discrete approximations to the continuous‐time problem. We prove the convergence of the algorithm and present some numerical results which compare its performance against that of linear network flow algorithms applied to a uniform discrete approximation of the continuous‐time problem.
Projected dynamical systems modeling and computation of spatial network equilibria
Authors: Nagurney Anna , Takayama Takashi , Zhang Ding
Published: May 2007

In this paper, we consider the price formulation—rather than the quantity formulation—of spatial network equilibria and introduce a projected dynamical system, whose set of stationary points corresponds to the set of solutions of the governing variational inequality problem. We then interpret the dynamical system as a tatonnement process in which the commodity prices and shipments are updated simultaneously. We propose an Euler‐type method for the computation of the commodity prices and trade patterns, provide convergence results, and demonstrate that the algorithm can be implemented on massively parallel architectures. The notable feature of the algorithm is that the prices and shipments can be computed independently and in closed form. Finally, we illustrate the performance of the implemented algorithm on the Thinking Machine's CM‐2 and CM‐5 architectures.
The helical cube network
Authors: Somani Arun K. , Thatte Sanjay
Published: May 2007

The binary cube is a popular interconnection structure due to its desirable properties such as symmetry, regularity, low diameter, and high fault‐tolerance characteristics. The biggest drawback of this structure, however, is that the number of nodes in this structure grows only as an integer power of two. To remove this deficiency, a number of alternatives have been suggested, each with some limitations. in this paper, we introduce a variation of this interconnection structure called the helical cube. The proposed structure withKnodes strives to preserve all desirable properties of the binary cube such as regularity, simplicity of routing, and fault tolerance (connectivity of the graph). It removes the restriction on the number of nodes being a power of two while maintaining connectivityc, where ⌊logK⌋ ≤c≤ ⌈logK⌉. The degree of each node remains either ⌈logK⌉ or ⌊logK⌋ depending on the location of a node and total number of nodes in the structure.
Bipartite regular graphs with fixed diameter
Authors: Broersma H. J. , Göbel F.
Published: May 2007

For given nonnegative integers k and D, we consider the problem of determining n0(k, D), The smallest number n for which there exists a k‐regular bipartite graph on n vertices with diameter D. We solve the problem for all pairs (k, D) with D ≢ 2 (mod 4) and D ≢ 3 (mod 4), for all pairs (k, D) with k even or k prime and D ≢ 3 (mod 4), for all pairs with D ≤ 9 or k ≤ 4, and for a few other pairs. in the remaining cases, we obtain lower and upper bounds for n0(k, D).
On the generalized minimum spanning tree problem
Authors: Myung Young‐Soo , Lee Chang‐Ho , Tcha Dong‐Wan
Published: May 2007

This paper considers the Generalized Minimum Spanning Tree Problem (GMSTP). Given an undirected graph whose nodes are partitioned into mutually exclusive and exhaustive node sets, The GMSTP is then to find a minimum‐cost tree which includes exactly one node from each node set. Here, we show that the GMSTP is NP‐hard and that unless P = NP no polynomial‐time heuristic algorithm with a finite worst‐case performance ratio can exist for the GMSTP. We present various integer programming formulations for the problem and compare their linear programming relaxations. Based on the tightest formulation among the ones proposed, a dual‐based solution procedure is developed and shown to be efficient from computing experiments.
Computing the 2‐median on tree networks in O(n lg n) time
Authors: Gavish Bezalel , Sridhar Suresh
Published: May 2007

Location of facilities on tree networks is an important problem in transportation and telecommunication systems. For tree networks, The best‐known algorithm to find 2‐medians has a time complexity of O(n2). By exploiting the properties relating the 1‐median and the 2‐medians in tree networks, and the properties inherent in tree structure, an improved algorithm is developed for computing the 2‐median. The time complexity of this algorithm is O(n lg n). The details of the algorithm are described along with an illustrative example.
Betrachtungen über die Planetenbewegung
Authors: Mohr† O.
Published: May 2007

Im Nachlasse des am 2. Oktober 1918 verstorbenen Vertreters der technischen Mechanik an der Dresdener Hochschule fand sich der folgende, aus seiner letzten Lebenszeit stammende Aufsatz. Wenn Dieser auch seinem mehr didaktischen Inhalt nach sich dem Rahmen der Zeitschrift nur schwer einfügt, so glaubte die Schriftleitung doch, mit der VeröffeNtlichung einer Ehrenpflicht gegenüber dem um die Wissenschaft hochverdienten Forscher genügen zu sollen.
Synthesis of the structured lipid 1,3‐dioleoyl‐2‐palmitoylglycerol from palm oil
Authors: Chen Ming‐Lung , Vali Shaik Ramjan , Lin Jih‐Yao , Ju Yi‐Hsu
Published: May 2007

Human milk fat contains 20–25% palmitic acid (16∶0) and 30–35% oleic acid (18∶1). More than 60% of the plamitic acid occurs at the sn‐2 position of the glycerol backbone. Palm oil is a rich source of both palmitic and oleic acids. The structured lipid 1,3‐dioleyl‐2‐palmitoylglycerol (OPO) is an important ingredient in infant formula. OPO was synthesized from palm oil by a three‐step method. In the first step, low‐temperature fractionation was applied to palm oil FA, yielding a palmitic acid‐rich fraction (87.8%) and an oleic acid‐rich fraction (96%). The palmitic acid content was further increased to 98.3% by transforming palmitic acid into ethyl palmitate. In the second step, esterification of ethyl palmitate and glycerol catalyzed by lipase Novozym 435 under vacuum (40 mm Hg) was employed for the synthesis of tripalmitin. Finally, OPO was obtained by the reaction of tripalmitin. Finally, OPO was obtained by the reaction of tripalmitin with oleic acid catalyzed by Lipase IM 60. In this final step, the TAG content in the product acylglycerol mixture was 97%, and 66.1% oleic acid was incorporated into TAG. Analysis of the FA composition at the sn‐2 position of TAG showed 90.7 mol% of palmitic acid and 9.3 mol% of oleic acid. OPO content in the product TAG was ca. 74 mol%. Thus, an efficient method was developed for the synthesis of OPO from palm oil.
Enzymatic pretreatment on rose‐hip oil extraction: Hydrolysis and pressing conditions
Authors: Concha J. , Soto C. , Chamy R. , Zúñiga M. E.
Published: May 2007

In a previous report [Zúñiga, M.E., J. Concha, C. Soto, and R. Chamy, Effect of the Rose Hip (Rosa aff. rubiginosa) Oil Extraction Cold‐Pressed Process, in Proceedings of the World Conference and Exhibition on Oilseed Processing, and Utilization, edited by R.F. Wilson, AOCS Press, Champaign, 2001, pp. 210–213], the authors showed that an enzymatic pretreatment of rose‐hip seeds, prior to oil extraction by cold pressing, improves the oil yield. In this work, we studied the effects of temperature and moisture during the enzymatic hydrolysis stage using two previously selected mixtures of commercial enzymes: (i) Olivex (mainly pectinase) plus Cellubrix (mainly cellulase), and (ii) Finizym (mainly β‐glucanase) plus Cellubrix (mainly cellulase) (all from Novozymes A/S, Madrid, Spain). In addition, we evaluated the effect of enzymatic hydrolysis on the oil extraction pressing rate at different operational pressures. Samples hydrolyzed enzymatically by either of the two commercial enzyme mixtures at 45°C and 30–40% moisture showed oil extraction yields up to 60%, an increase of greater than 50%, as compared with control samples in which the enzyme solutions were replaced by water. Both the oil extraction rate and yield by pressing increased when enzymatic pretreatment was applied. The oil extraction yield increased slightly when the operation pressure was elevated; however, when the sample was preheated, the oil extraction yield was greatly increased, especially for enzyme‐treated samples. Results confirmed the importance of temperature and moisture as enzymatic hydrolysis parameters that improve rose‐hip oil extraction yields in the cold‐pressing process. When pressing was carried out after preheating enzymatically treated samples, it was possible to increase the oil extraction yield to 72% compared with the control without preheating, which resulted in a 46% oil yield.
An enzymatic method for the synthesis of mixed‐acid phosphatidylcholine
Authors: Adlercreutz Dietlind , Wehtje Ernst
Published: May 2007

The enzymatic synthesis of PC with decanoic acid in the sn‐1 and hexanoic acid in the sn‐2 position is described. The procedure comprises the following enzymatic steps: (i) treatment of egg yolk with phospholipase A2 (PLA2) to hydrolyze egg yolk PC to 1‐acyl lysophosphatidylcholine (LPC); (ii) esterification of 1‐acyl LPC with hexanoic acid catalyzed by PLA2 to yield PC with hexanoic acid in the sn‐2 position; (iii) removal of the FA in the sn‐1 position by lipase‐catalyzed ethanolysis to yield 2‐hexanoyl LPC; and finally (iv) introduction of decanoic acid in this position by lipase‐catalyzed esterification of 2‐hexanoyl LPC to yield 1‐decanoyl‐2‐hexanoyl‐PC. Two egg yolks with a weight of 16 g were required to obtain 160 mg of the desired product. The chemical purity of the PC product and the positional purity of the FA were around 99%. The method is applicable for the synthesis of other mixed‐acid PC species as well.
Preparation of laurel oil alkanolamide from laurel oil
Authors: Kolancilar Hakan
Published: May 2007

A low‐temperature synthesis of laurel oil alkanolamides directly from laurel oil and ethanolamine was carried out in essentially quantitative yields. The ethanolamine/laurel oil molar ratio used was 10∶1. Even though amine served as a catalyst in the reaction, we used sodium methoxide at a ratio of 0.2–2% as a second catalyst. The reaction was complete in 1–9 h at room temperature. The identity of the amide was confirmed by IR and 13C NMR spectroscopy.
Comparison of steam and nitrogen in the physical deacidification of soybean oil
Authors: Decap Philippe , Braipson‐Danthine Sabine , Vanbrabant Béatrice , De Greyt Wim , Deroanne Claude
Published: May 2007

Deacidification in physical refining is one of the most sensitive steps in refining edible vegetable oils because of its large impact on the quality of the oil. The removal of volatile compounds such as FFA is accomplished at elevated temperatures and a high vacuum with a stripping gas, usually steam. The aim of this work was to verify, at the laboratory level, the advantages of using an alternative stripping gas, nitrogen, instead of steam. An ideal vapor‐liquid equilibrium model (IVLE) was used to compare the stripping capacities of steam and nitrogen and to analyze the effects of various operational parameters (temperature, pressure, amount of stripping gas) on the residual acidity of the oil. There was no clear evidence that nitrogen showed a higher capacity to strip FFA than steam. The IVLE model seemed suitable to describe FFA laboratory distillation by using steam or nitrogen, provided the final residual content of FFA was not too low.
A single amino acid in the PSPG‐box plays an important role in the catalytic function of CaUGT2 (Curcumin glucosyltransferase), a Group D Family 1 glucosyltransferase from Catharanthus roseus
Authors: Masada Sayaka , Terasaka Kazuyoshi , Mizukami Hajime
Published: May 2007

Curcumin glucosyltransferase (CaUGT2) isolated from cell cultures of Catharanthus roseus exhibits unique substrate specificity. To identify amino acids involved in substrate recognition and catalytic activity of CaUGT2, a combination of domain swapping and site‐directed mutagenesis was carried out. Exchange of the PSPG‐box of CaUGT2 with that of NtGT1b (a phenolic glucosyltransferase from tobacco) led to complete loss of enzyme activity in the resulting recombinant protein. However, replacement of Arg378 of the NtGT1b PSPG‐box with cysteine, the corresponding amino acid in CaUGT2, restored the catalytic activity of the chimeric enzyme. Further site‐directed mutagenesis revealed that the size of the amino acid side‐chain in that particular site is critical to the catalytic activity of CaUGT2.
The Ndc80 complex: Hub of kinetochore activity
Authors: Ciferri Claudio , Musacchio Andrea , Petrovic Arsen
Published: May 2007

Kinetochores are protein scaffolds coordinating the process of chromosome segregation in mitosis. Kinetochore components are organized in functionally and topologically distinct domains that are designed to connect the sister chromatids to the mitotic spindle. The inner kinetochore proteins are in direct contact with the centromeric DNA, whilst the outer kinetochore proteins are responsible for binding to spindle microtubules. The conserved Ndc80 complex is implicated in several essential outer kinetochore functions, including microtubule binding and control of a safety device known as the spindle assembly checkpoint. Here, we describe how current work is contributing to unravel the complex endeavors of this essential kinetochore complex.
A 5-1/2-dimensional theory for fast and accurate evaluation of the cyclotron resonance heating using a real-space wave representation
Authors: Park Gunyoung , Chang C. S.
Published: May 2007

The cyclotron resonance heating rate in a plasma has been evaluated so far from a five-dimensional (5D) quasilinear model because the 6D evaluation is prohibitively expensive. However, the quasilinear approach as applied to the cyclotron resonance heating has fundamental difficulties in evaluating the net effect from a large number of coupled wave modes (leading to strong spatial wave inhomogeneity) since the theory is built on the Fourier space wave representation, and does not include the regular nonlinear particle dynamics within a resonance passing event since the theory is based on the unperturbed orbit theory. A new 5-1/2D theory is formulated for evaluation of a more accurate resonant particle dynamics using the real-space wave representation, which overcomes the shortcomings of the quasilinear cyclotron resonance heating theories by reproducing the 6D physics at the 5D computing speed.
Optical and electrical characterizations of self-assembled CdS nanorods—polyaniline composites
Authors: Dutta Kousik , De Sukanta , De S. K.
Published: May 2007

The aligned CdS nanorods are obtained by dispersing CdS in the conducting polyaniline matrix. The rods are about 50 nm in diameter and 400 nm in length. The significant changes of electronic absorption spectra of CdS nanorods and conducting polyaniline indicate the strong interaction between them. CdS—Polyaniline nanocomposites exhibit a three-dimensional Mott’s hopping process in the electrical conduction. Temperature variation of frequency dependent conductivity implies the correlated barrier hopping. The barrier height increases with the content of CdS.
Effect of chain length on fragility and thermodynamic scaling of the local segmental dynamics in poly(methylmethacrylate)
Authors: Casalini R. , Roland C. M. , Capaccioli S.
Published: May 2007

Local segmental relaxation properties of poly(methylmethacrylate) (PMMA) of varying molecular weight are measured by dielectric spectroscopy and analyzed in combination with the equation of state obtained from PVT measurements. Significant variations of glass transition temperature and fragility with molecular weight are observed. In accord with the general properties of glass-forming materials, single molecular weight dependent scaling exponent γ is sufficient to define the mean segmental relaxation time τα and its distribution. This exponent can be connected to the Grüneisen parameter and related thermodynamic quantities, thus demonstrating the interrelationship between dynamics and thermodynamics in PMMA. Changes in the relaxation properties (“dynamic crossover”) are observed as a function of both temperature and pressure, with τα serving as the control parameter for the crossover. At longer τα another change in the dynamics is apparent, associated with a decoupling of the local segmental process from ionic conductivity.
Temperature-dependent structural and optical properties of SnS films
Authors: Koteeswara Reddy N. , Hahn Y. B. , Devika M. , Sumana H. R. , Gunasekhar K. R.
Published: May 2007

The structural and optical properties of SnS films deposited on glass substrates have been studied at different temperatures under a vacuum of 10−6 Torr. At room temperature, the SnS films showed orthorhombic crystal structure with lattice parameters of a=0.424, b=1.107, and c=0.3974 nm. These films also showed an optical band gap of ∼1.47 eV with a high absorption coefficient, ∼105 cm−1. X-ray diffraction studies at different temperatures (100−598 K) demonstrated that the structure of the SnS films remains constant. However, the volume of the unit cell of SnS films increased with the increase of temperature. It might be due to the expansion of the lattice. The effect of temperature (4−303 K) on the band gap of SnS films is also marginal (∼0.03 eV). It indicates that the SnS films are optically stable even at very low temperatures due to its stabilized structure. Therefore, SnS films offer an opportunity to be used as alternative semiconducting materials as active layers for the fabrication of optoelectronic devices.
Parietal stimulation destabilizes spatial updating across saccadic eye movements
Authors: Morris Adam P. , Chambers Christopher D. , Mattingley Jason B.
Published: May 2007

Saccadic eye movements cause sudden and global shifts in the retinal image. Rather than causing confusion, however, eye movements expand our sense of space and detail. In macaques, a stable representation of space is embodied by neural populations in intraparietal cortex that redistribute activity with each saccade to compensate for eye displacement, but little is known about equivalent updating mechanisms in humans. We combined noninvasive cortical stimulation with a double-step saccade task to examine the contribution of two human intraparietal areas to transsaccadic spatial updating. Right hemisphere stimulation over the posterior termination of the intraparietal sulcus (IPSp) broadened and shifted the distribution of second-saccade endpoints, but only when the first-saccade was directed into the contralateral hemifield. By interleaving trials with and without cortical stimulation, we show that the shift in endpoints was caused by an enduring effect of stimulation on neural functioning (e.g., modulation of neuronal gain). By varying the onset time of stimulation, we show that the representation of space in IPSp is updated immediately after the first-saccade. In contrast, stimulation of an adjacent IPS site had no such effects on second-saccades. These experiments suggest that stimulation of IPSp distorts an eye position or displacement signal that updates the representation of space at the completion of a saccade. Such sensory-motor integration in IPSp is crucial for the ongoing control of action, and may contribute to visual stability across saccades.