bluuebunny/crossref_metadata_2025_split huggingface dataset:
Monocyte activation in response to polyethylene glycol hydrogels grafted with RGD and PHSRN separated by interpositional spacers of various lengths
Authors: Schmidt David Richard , Kao Weiyuan John 
Published: May 2007

AbstractPolyethylene glycol (PEG) is often cited as a “stealth” polymer, capable of resisting both protein adsorption and cell adhesion. By extension, PEG would then be expected to limit the host response. Monocyte‐derived macrophages play an integral role in inflammation, and thus their response to a material can potentially dictate the overall host response to a biomaterial. In the present study, monocyte responses following interaction with a photopolymerized PEG hydrogel were compared with those from standard tissue culture polystyrene (TCPS). Additionally, the effect of the spacing between RGD and PHSRN, the corresponding synergy sequence on fibronectin (FN), was evaluated using peptides with differing spacer lengths grafted to the PEG hydrogel. Monocyte adherent density on the PEG‐only hydrogel was comparable with that of TCPS; however, the secretion of the proinflammatory molecules interleukin‐1β (IL‐1β), tumor necrosis factor‐α (TNF‐α), and granulocyte‐macrophage colony stimulating factor (GM‐CSF) increased dramatically following monocyte interaction with PEG‐only hydrogels as compared with TCPS. The matrix metalloproteinase‐2 (MMP‐2) concentration was similar for all surfaces, while both the matrix metalloproteinase‐9 (MMP‐9) and FN concentrations were above the range of the assay for all substrates. Cell density was higher on the PHSRNG13RGD grafted substrate as compared with PHSRNG6RGD, but neither sequence increased cell density versus RGD alone. Although protein concentration did sometimes vary with different peptides, this variation was minimal in comparison with the surface effects between TCPS and the PEG‐only hydrogel. This study explores the roles of PEG and FN‐derived peptides on monocyte activation. © 2007 Wiley Periodicals, Inc. J Biomed Mater Res 2007
SER(R)S of porphyrins on Ag nanoparticles immobilized by silane: a unique way to obtain free‐base porphyrin spectra
Authors: Molnár Peter , Procházka Marek 
Published: May 2007

AbstractWe measured the surface‐enhanced resonance Raman scattering (SER(R)S) spectra of 5,10,15,20‐tetrakis (1‐methyl‐4‐pyridyl)porphyrin (TMPyP) by using solid SERS‐active substrates: Ag nanoparticles immobilized by aminosilane on glass plates. We report the surprising result that by using such substrates it is possible to obtain SER(R)S spectra of porphyrins in the unperturbed free‐base form, although by using silver nanoparticles directly in solution, the porphyrin molecules are completely metalated. We suggest that silane used for nanoparticle immobilization modifies the surface properties and, therefore, makes porphyrin metalation impossible. Copyright © 2007 John Wiley & Sons, Ltd.
Effects of a CRF2R agonist and exercise on mdx and wildtype skeletal muscle
Authors: Hall Julie E. , Kaczor Jan J. , Hettinga Bart P. , Isfort Robert J. , Tarnopolsky Mark A. 
Published: May 2007

AbstractCorticotrophin‐releasing factor 2 receptor (CRF2R) agonists prevent muscle atrophy due to immobilization, denervation, and corticosteroid‐induced muscle atrophy in wildtype mice. We hypothesized that a CRF2R agonist will increase skeletal muscle mass in mdx mice. Mdx (C57BL/10ScSn‐Dmdmdx) and wildtype (C57BL/6) mice were divided into four groups: sedentary placebo, sedentary CRF2R agonist, exercised placebo, and exercised CRF2R agonist. Mice exercised on a treadmill twice weekly for 30 min (8–12 m/min, 8 weeks). Muscle and heart weights, serum creatine kinase, and γ‐glutamyltransferase activities were measured. The CRF2R agonist increased extensor digitorum longus and soleus muscle weights (P < 0.05) in wildtype and mdx mice. Sedentary mdx CRF2R and exercised mdx placebo mice had lower serum creatine kinase activity than sedentary mdx placebo mice. CRF2R‐treated mice had decreased heart weights compared to placebo‐treated mice. We conclude that CRF2R agonists should be further evaluated as a potential therapy for dystrophinopathies. Muscle Nerve, 2007
Efficient storage of nonadaptive routing tables
Authors: Manber Udi , McVoy Lawrence 
Published: May 2007

AbstractAn algorithm for improving storage utilization for nonadaptive routing tables in point‐to‐point networks is presented. It allows storage vs. access time tradeoffs. The algorithm is quite general, and it can be used for other applications to improve storage in tree‐like structures. The algorithm was applied to the UUCP routing tables resulting in a threefold storage improvement.
Polymatroidal flow network models with multiple sinks
Authors: Federgruen A. , Groenevelt H. 
Published: May 2007

AbstractWe consider the polymatroidal flow network model which incorporates two important extensions of the standard maximal flow problem: general concave objective functions of the vector of supplies to a collection of sinks, as well as polymatroidal capacity restrictions on sets of arcs emanating from or pointing to a common node. A number of important applications are reviewed. We show that in this general model the set of feasible supply vectors is itself a polymatroid, and that an optimal solution may be determined by at most 2|V*| — 1 maximum flow computations and optimizations of the objective over a single budget constraint, where |V*| is the number of sinks. Also, it is shown that for the most common types of polymatroidal structures an equivalent flow network can be constructed on an expanded graph but with capacity restrictions on individual arcs only. This transformation allows for the use of classical maximum flow procedures resulting in an often dramatic reduction in complexity.
A survey of gossiping and broadcasting in communication networks
Authors: Hedetniemi Sandra M. , Hedetniemi Stephen T. , Liestman Arthur L. 
Published: May 2007

AbstractGossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network. In gossiping every person in the network knows a unique item of information and needs to communicate it to everyone else. In broadcasting one individual has an item of information which needs to be communicated to everyone else. We review the results that have been obtained on these and related problems.
An SST‐based algorithm for the steiner problem in graphs
Authors: Beasley J. E. 
Published: May 2007

AbstractIn this paper we consider the Steiner problem in graphs which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graphs. We present a formulation of the problem as a shortest spanning tree (SST) problem with additional constraints. By relaxing thses additional constraints in a lagrangean fashion we obtain a lower bound for the problem based upon the solution of an unconstrained SST problem. Problem reduction tests derived from both the original problem and the lagrangean relaxation are given. Incorporating the bound and the reduction tests into a tree search procedure enables us to solve problems involving the connection of up to 1250 vertices in a graph with 62500 edges and 2500 vertices.
Some properties of 2‐threshold graphs
Authors: Hammer P. L. , Mahadev N. V. R. , Peled U. N. 
Published: May 2007

AbstractA 2‐threshold graph is defined to be the edge‐union of two threshold graphs. We prove that all chordless cycles of size at least 5 and their complements are forbidden for 2‐threshold graphs. We also obtain a sufficient condition for a 2‐threshold graph to be a comparability graph. Finally, we show that 2‐threshold graphs can have at most three cutpoints and obtain efficient algorithms to recognize, decompose and obtain a maximum stable set of 2‐threshold graphs with exactly three cutpoints.
Minimum order graphs with specified diameter, connectivity, and regularity
Authors: Krishnamoorthy V. , Thulasiraman K. , Swamy M. N. S. 
Published: May 2007

AbstractRelationships among graph invariants such as the number of vertices, diameter, connectivity, maximum and minimum degrees, and regularity are being studied recently, motivated by their usefulness in the design of fault‐tolerant and low‐cost communication and interconnection networks. A graph is called a (d,c,r) graph if it has diameter d, connectivity c, and regularity r. The minimum number of vertices in (d, 1,3), (d,2,3), (d,3,3), and (d,c,c) graphs have been reported in the literature. In this paper, the minimum number of vertices in a (d,c,r) graph with r > c is determined, thereby exhausting all the possible choices of values for d, c, and r. Our proof is constructive and hence we get a collection of optimal (d,c,r) graphs.
Transitively reduced and transitively closed event networks
Authors: Mrozek Marian 
Published: May 2007

AbstractWe present the notion of a generalized inverse of a digraph. The notion includes two different kinds of event networks, both discussed in literature. We show how different techniques used separately in both special cases can be applied to the general case. We prove that the problem of minimization of the number of dummy arcs among al event networks having the minimum number of vertices is polynomially transformable to a certain covering problem. We use the transformation method to provide a necessary and sufficient condition for a certain suboptimal solution to the problem to be optimal in general. We show that the verification of this condition can be done in polynomial time.
Extremal connectivity and vulnerability in graphs
Authors: Doty Lynne L. 
Published: May 2007

AbstractIf a practical network is modelled as a graph in which the lines are perfect but the points may fail then a primary measure of vulnerability is the point connectivity of the graph and one possible secondary measure of vulnerability is the number of minimum point disconnecting sets. The graph shold have the maximum possible point connectivity and the minimum number of point disconnecting sets. A lower bound for the number of minimum point disconnecting sets is derived by identifying points with identical adjacencies.
Optimal enclosing regions in planar graphs
Authors: Bienstock Daniel , Monma Clyde L. 
Published: May 2007

AbstractIn this paper we study the problem of finding a minimum‐weight collection of edges in a planar graph which separates a given set of vertices from the outer face. This problem has two variants: either a given embedding is specified, or the best possible embedding is to be found. We present polynomial‐time algorithms for each case. We show how to use these results to recognize a special case of the steiner tree problem in graphs which is polynomially solvable. A closely related problem is shown to be NP‐complete.
Implementing an “exact” Newton method for separable convex transportation problems
Authors: Klincewicz John G. 
Published: May 2007

AbstractConvex transportation problems represent an important special class of convex network flow problems, with particular applications in telecommunications, economics and engineering. This paper describes an implementation of an “exact” Newton algorithm for separable convex transportation problems. Previously in the literature, only approximate Newton algorithms had been described for the general case of convex network flow problems. The special structure of the transportation problem is used to simplify computation of dual multiplier estimates. In general, this would require factorization of a square matrix of dimension n + m − 1, were n is the number of sources and m is the number of sinks. By exploiting structure, the work of factorization is limited to a square matrix of dimension n − 1 or m − 1, whichever is smaller. Some computational experience is described. We also note an analogy between this Newton algorithm for convex problem and a particular variant of Karmarkar's algorithm for linear problems.
Triconnected decomposition for computing K‐terminal network reliability
Authors: Wood R. Kevin 
Published: May 2007

AbstractLet R(Gk) denote the probability that a subset of vertices K in the undirected graph G = (V, E) can communicate when the edge of G fail independently with known probabilities. Suppose that Gk contains as separting pair of vertices {u, v} such that Gk= G̃k̃ ∪ Ǧǩ, Ṽ ∩ V̂ ={u v}, Ẽ ∩ Ê = ø, |Ẽ| ⩾ 2, and |Ê| ⩾2. It is shown that Ĝk may be replaced by a chain χ of at most three edges between u and v such that R(Gk) = ΩR ((G̃ ∪ χ)k̃′) where Ω is a derived constant and K̃′ is defined by the procedure. The failure probabilities of the edges in χ and the value of Ω are shown to be computable by evaluating the reliability of one of four variants of Ĝk̂. Minimal components Ĝk̂ can be efficiently found using triconnected decomposition and the above procedure embedded within a recursive factoring algorithm for computing K‐terminal reliability. Conditions are derived which guarantee the new algorithm is at least as good as a pure factoring algorithm, and an example shows that the new algorithm can be exponentially better.
Connected reorientations of mixed multigraphs
Authors: Shi Weigeng , Juels Ronald J. 
Published: May 2007

AbstractWe study here the problem of reorienting the directed edges of mixed multigraphs so as to establish or preserve reachability, which may be destroyed by edge removal. We develop a linear time/space algorithm which tests whether reorienting designated directed edges can reestablish reachability, and which constructs such a reorientation whenever possible. We also develop a linear time/space algorithm which, when reachability has been destroyed by the removal of a single edge, optimally restores reachability through the reversal of selected edges. Finally, we show the reliability of a graph allowing reversals to be twice that of a graph for which reversals are not permitted.
On graphs with polynomially solvable maximum‐weight clique problem
Authors: Balas Egon , Yu Chang Sung 
Published: May 2007

AbstractWe give a new bound on the number of maximal cliques in a graph, along with a bound on the length of odd antiholes that the graph can contain. Based on these bounds we then identify a family of graphs with polynomially solvable maximum weight clique problem, using the edgebicoloring approach developed in a recent paper by Balas, Chvatal, and Nesetril.
A functional equation for finding the largest expected capacity of a graph
Authors: Sancho N. G. F. 
Published: May 2007

AbstractGiven a graph in which every arc (i, j) has two numbers ρij and Cij associated with it representing the reliability and capacity, respectively, a dynamic programming formulation is derived for finding the path from any node i to terminal node N with the largest expected capacity. It is shown that the functional equation obtained may not necessarily be governed by the principle of optimality.
On optimal cycle bases of graphs for mesh analysis of networks
Authors: Kaveh A. 
Published: May 2007

AbstractAn algorithm is developed for the selection of a cycle basis of a graph which corresponds to a highly sparse cycle adjacency matrix, hence providing an efficient means for the mesh analysis of networks. Unlike the existing methods, this algorithm reduces the overlaps of the cycles instead of their lengths. The results are compared with those of the previous methods through some examples. The cycles are also ordered to obtain banded cycle adjacency matrices.
Exact cuts in networks
Authors: Provan J. Scott , Kulkarni V. G. 
Published: May 2007

AbstractAn exact cut in a source‐sink network is a set of arcs which interesects each source‐sink path in exactly one arc. This paper investigates the problem of finding a maximum weight exact cut in a network. The problem is shown to be polynomially equivalent to that of determining the relevant arcs (arcs on at least one source‐sink path) in the network and is NP‐hard for general directed networks. There are, however, several important classes of network—including undirected networks—for which polynominal time algorithms do exist to solve the maximum weight exact cut problem.
Analysis of a flow problem with fixed charges
Authors: Hochbaum Dorit S. , Segev Arie 
Published: May 2007

AbstractThis article addresses a problem that comes up frequently in network design, and routing. A source is to distribute flows to nodes in the network. Sending flow along an arc involves a fixed cost for using the arc and a variable cost for each ujnit of flow. We show tht the problem of finding a minimum cost collection of arcs along which flows will be directed is an NP‐hard problem. We describe a procedure of solving the problem to optimality and several heuristics. In particular, we conclude that the use of polynomially derived Lagrange multipliers yields good quality solutions and bounds and can be implemented in a distributed processing mode in the network.
Networks synthesis and optimum network design problems: Models, solution methods and applications
Authors: Minoux M. 
Published: May 2007

AbstractThis paper is intended as a survey in the area of network synthesis and optimum network design, which, in view of the importance and variety of the underlying applications, has attraced, since the early 1960s, much interest in the Operations Research community. Indeed, if the first models were studied in connection with telecommunication networks, the range of applications kept on getting broader and broader, including transportation networks, computer and teleprocessing networks, energy transport systems, water distribution networks, etc. However, beyond the apparent diversity of practical situations involved, most of these applications can be accounted for (modulo possibly a few minor adaptations), by a rather limited number of basic models. One of the main purposes of this paper is to provide the reader with a relevant classification of the area which will help him identify the fundamental structure of the problem (if any) he has to cope with, and relate it to already published work. In order to obtain a fairly good coverage of the matter, we have thus been led to identify three basic models aroung which the whole paper is organized: a general model using minimum cost multicommodity flows (Section 2); models in terms of tree‐like networks (Section 3); models using nonsmultaneous single‐commodity or multicommodity flows (Section 4). In each bcase the most important variants of the basic models have been surveyed with the purpose of providing as much information as possible concerning (a) the various contexts of applications from which the problem arose; (b) the main computational methods proposed in the literature for solving it, with emphasis on those techniques which appear at present, to be most efficient or promising.
How to find a battleship
Authors: Fiat Amos , Shamir Adi 
Published: May 2007

AbstractConsider a “sea” of M squares which contains (at some unknown location) a “battleship” of K squares. Both the sea and the battleship can assume any rectangular shape. Our goal is to find the battleship by probing at least one of its squares. In this paper we describe a deterministic strategy for this problem which is guaranteed to locate the battleship in at most c1 M/K probes, where c1 ≈︁ 3.065.
Designing satellite communication networks by zero—one quadratic programming
Authors: Helme Marcia P. , Magnanti Thomas L. 
Published: May 2007

AbstractIn satellite communications networks, distinctive facilities called homing stations perform special transmission functions. Local demand nodes clustered around each homing station communicate with each other via a local switch at the homing station; demand nodes in different cluster communicate with each other via satellite earth stations at the homing stations. Designing such a communication network requires choices on the locations of the earth stations and on the assignments of demand nodes to the local clusters at the earth stations. We formulate this problem as a zero‐one quadratic facility location problem and transform it into an equivalent zero‐one integer linear program. Computational experience on real data shows that a branch and bound procedure is effective in solving problems with up to 40 demand nodes (major cities) and that the solutions that this algorithm finds improve considerably upon management generated solutions. We also show that a greedy add heuristic, as implemented on an IBM PC, consistently generates optimal or near‐optimal solutions.
On mean distance in certain classes of graphs
Authors: Hendry George R. T. 
Published: May 2007

AbstractThe mean distance, μ(G), of a graph G is the arithmetic mean of the distances in G. Upper and lower bounds for the mean distance of a self‐complementary graph of given order are obtained and the extremal grpahs are determined. It is shown that if t ≥ 2 is rational, then there exist (1) graphs with arbitrarily low or high edge density, (2) bipartite graphs and (3) oriented graphs with mean distance equal to t, and also (4) trees and (5) tournaments with mean distance arbitrarily close to t. A number of open problems are mentioned.
Statistical procedures for estimating branch flows and total network flow
Authors: Wells Charles E. , Evans James R. 
Published: May 2007

AbstractThe problem fo estimating branch flows and total network flow in a directed acyclic network is important in diverse applications, such as: (1) in the measurement of rainfall and water run off and (2) in cash control as cash receipts move through an accounting system. In this paper, a variety of network flow estimation problems are examined, where the measurement errors of the observed branch flows may be correlated. Procedures are presented which produce branch flow estimates that conserve flow when observations of flow are available on all network branches and which produce total network flow estimates when observations of flow are available on only a subset of network branches. The latter procedure uses observed flows through proper cut sets. Also included is a discussion of a tractable method of computing biased total network flow estimates. These biased estimates have the potential advantage of having a relatively small variance. All of the estimation procedures presented derive estimates from the solution of appropriately formaulated mathematical programs whose objective function is a quadratic form. An example is included to illustrate the ease of use of the proposed estimation procedures.
Message complexity versus space complexity in fault tolerant broadcast protocols
Authors: Moran Shlomo 
Published: May 2007

AbstractLet N be a network of asynchronous processors, viewed as vertices, communicating by sending messages over unreliable unidirectional edges, and let r be a specified vertex in N. We consider the problem of constructing efficient and reliable protocols to broadcast messages from r to all other vertices of N: Suppose that for some vertex v in N, at least k edges must be deleted in order to disconnect v from r; we say that a protocol PR, this message will eventually reach v. A protocol is faithful if it is reliable fro all vertices of the network. A general lower bound on the message complexity of faithful protocols, which is at most linear in the network size, is given. It is also shown that this bound can always be achieved by protocols which use the local memories of the vertices to record messages. On the other hand, it is shown that for certain networks, all faithful protocols that use no memory for local computations have a message complexity which is exponential in the network sixe. A characterization of networks that hve faithful protocosl with optimal message and space complexities is also given.