bluuebunny/crossref_metadata_2025_split huggingface dataset:
An optimal 2‐FT realization of binary symmetric hierarchical tree systems
Authors: Kwan C. L. , Toida S. 
Published: May 2007

AbstractFault tolerance is expected to become the major concern for complex systems consisting of many computing or processing units. Given a basic nonredundant system of computing units, the problems are to determine the minimum extra units and connections required and their structures so that the resulting system would tolerate k faulty units. These problems have been formulated and solved for some special types of systems by Hayes using a graph model. In this paper, we present a procedure for designing an optimal 2‐FT (two‐fault‐tolerant) structure for binary symmetric hierarchical tree systems.
Modular decomposition and reliability computation in stochastic transportation networks having cutnodes
Authors: Shogan Andrew W. 
Published: May 2007

AbstractConsider a flow network having random arc capacities and having associated with each node n a “supply‐demand random variable” Yn whose absolute value equals the supply available at the node when Yn assumes a non‐negative value and the demand required by the node when Yn assumes a nonpositive value. A fundamental problem is the computation of the reliability R, that is, the probability that the random variables will assume values that permit a feasible flow. Upon adapting the graph‐theoretic concepts of “cutnode” and “block,” it is possible to identify a “block‐module,” an independent, nontrivial subnetwork that has one and only one node (the “cutnode”) connected to nodes outside the subnetwork. The reliability of the network will increase by a known factor after a “block‐modular decomposition” that consists of a transformation of the cutnode's supply‐demand random variable and the deletion of the remainder of the block module. Provided the original network possesses at least one block module, R can be determined from a sequence of block‐modular decompositions that reduce the original network to a single node whose reliability is easily computed. Computational experience with a computer implementation of such a decomposition method is reported, and the application of the method to the analysis of electrical power networks is included.
The complexity of finding maximum disjoint paths with length constraints
Authors: Itai A. , Perl Y. , Shiloach Y. 
Published: May 2007

AbstractThe following problem is considered: Given an integer K, a graph G with two distinct vertices s and t, find the maximum number of disjoint paths of length K from s to t. The problem has several variants: the paths may be vertex‐disjoint or edge‐disjoint, the lengths of the paths may be equal to K or bounded by K, the graph may be undirected or directed. It is shown that except for small values of K all the problems are NP‐complete. Assuming P ≠ NP, for each problem, the largest value of K for which the problem is not NP‐complete is found. Whenever a polynomial algorithm exists, an efficient algorithm is described.
Polynomial algorithms for estimating network reliability
Authors: Zemel Eitan 
Published: May 2007

AbstractWe consider the problem of calculating the best possible bounds on the reliability of a system given limited information about the joint density function of its components. We show that a polynomial algorithm for this problem exists iff such an algorithm exists for a certain related problem of minimizing a linear objective function over a clutter. We give numerous examples of network as well as other problems for which the algorithm runs in polynomial time. We also use our construction to prove NP‐hardness for others.
A procedure for dispatching moving mobile servers
Authors: Berman O. , Rahnama M. Rasty 
Published: May 2007

AbstractThis article deals with some dispatching aspects of a system in which the dispatcher, in addition to stationary service units, has also the option to assign service units in motion. The nonstationary servers leave their home location at different times and move on different paths. The response time is the shortest time path of a server from the incident. The objective is to identify efficiently the appropriate unit to dispatch to a random incident. The analysis ends as soon as one of the servers is dispatched. The paper contains an efficient procedure based on the notion of the general time path. The general time path is a single path in which we superimpose the various different paths of all the moving servers. This simplifies the analysis since once the general time path is constructed it contains all the information that is provided by all those different paths. The procedure shows how to divide the general time path to disjoint segments according to the server which is closest to the incident (in each one of the segments exactly one identifiable server is closest to the incident).
Constructing a minimal‐cost spanning tree subject to resource constraints and flow requirements
Authors: Shogan Andrew W. 
Published: May 2007

AbstractConsider a network in which one node is a source having an infinite supply of a commodity, and every other node is a sink having a known constant demand. Furthermore, associated with each potential arc of the network are the following known constants: the cost of constructing the arc, the amount of each scarce resource consumed during the construction of the arc, and the flow capacity of the arc. Given the above known constants as well as the available supply of each of the scarce resources, the problem is to construct a minimal‐cost spanning tree subject to the limitations on the consumption of the scarce resources and the requirement that there exists a flow from the source satisfying the demands at the sinks without exceeding any arc capacity. This paper discusses the solution of such a problem by a branch and bound algorithm based on Lagrangian relaxation. Also included are applications of the problem, extensions of the problem, and a report on preliminary computational experience with a computer implementation of the algorithm.
An algorithm for finding a large independent set in planar graphs
Authors: Chiba Norishige , Nishizeki Takao , Saito Nobuji 
Published: May 2007

AbstractA subset of the vertices of a graph is independent if no two vertices in the set are adjacent. M. O. Albertson proposed an algorithm for finding an independent set that contains more than two‐ninth of the vertices of a planar graph. Refining his algorithm, we give an O(n2) algorithm for the same purpose.
I‐Colorings, I‐Phasings, and I‐Intersection assignments for graphs, and their applications
Authors: Opsut Robert J. , Roberts Fred S. 
Published: May 2007

AbstractThis paper studies set assignments on graphs, functions assigning a set S(x) to each vertex x of a graph, and specifically set assignments where each set is a real interval, perhaps of specified minimum length. Such set assignments arise in applied problems dealing with fleet maintenance, mobile radio frequency assignment, task assignment, traffic phasing, banquet preparation, and computer storage optimization. These problems are briefly discussed. They are translated into problems of finding a set coloring [a set assignment in which an edge between x and y implies that S(x) and S(y) are disjoint], a set phasing [a set coloring of the complementary graph], or a set intersection assignment. The paper presents methods for finding set colorings, phasings, and intersection assignments in which the measure of the union of the intervals S(x) is minimized or in which the sum of the lengths of the S(x) is maximized.
Dynamic matchings and quasidynamic fractional matchings. II
Authors: Orlin James B. 
Published: May 2007

AbstractConsider a directed graph G in which every edge has an associated real‐valued distance and a real‐valued weight. The weight of an undirected circuit of G is the sum of the weights of the edges, whereas the distance of an undirected circuit is the sum of the distances of the forward edges of the circuit minus the sum of the distances of the backward edges. A trivial circuit is a two‐edge circuit in which one edge of G appears twice on the circuit. A quasidynamic fractional matching (or Q‐matching) is a collection of vertex‐disjoint circuits such that each circuit is either trivial or else it is an odd circuit whose distance is nonzero. The G‐matching problem is to find a Q‐matching that maximizes the sum of the weights of its circuits. The Q‐matching problem generalizes both the matching problem and the fractional matching problem. Moreover, the dynamic matching problem, which is a matching problem on an infinite dynamic (time‐expanded) graph, is linearly transformable to the Q‐matching problem, as shown in Part I of this paper. In this paper we solve the Q‐matching problem by generalizing Edmonds' blossom algorithm. In fact, all of the major components of the blossom algorithm‐including alternating trees, augmentations, shrinking, and expanding‐are appropriately generalized to yield a running time that is proportional to that for the weighted matching problem. Furthermore, if all edge distances are equal to zero, this new algorithm reduces to the blossom algorithm.
On multicommodity flows in planar graphs
Authors: Hassin Refael 
Published: May 2007

AbstractOkamura and Seymour recently proved two properties of multicommodity flows in undirected planar networks where all the sources and the sinks are on a common face of the underlying graph. One is that a feasible solution is guaranteed whenever each cut's capacity is at least as large as the cut's demand. The second is that if all demands and capacities are integers then the flow values may be chosen half‐integer‐valued. In this paper we use the first property to construct two computational procedures; one examines the existence of a feasible flow, and the other constructs such a flow if one exists. We also show that the construction procedure can be used as an alternative proof to the above properties. Finally we show, by presenting counterexamples, that the half‐integrality property does not necessarily hold when either the graph cannot be drawn in the plane with all sources and sinks on a common face, or the graph is directed.
Updating routing tables after resource failure in a distributed computer network
Authors: Johnson Marjory J. 
Published: May 2007

AbstractThis paper is an analysis of overhead required by the MERIT routing table update algorithm after failure of a single network resource. The number of update messages sent by each node during the update process is used as the measure of update overhead. Both synchronous behavior and asynchronous behavior of the MERIT algorithm are considered. The number of messages required for synchronous update is shown to be an upper bound for the number of messages required if update occurs asynchronously. The effect of network topology on update overhead is discussed. Finally, some implementation suggestions aimed at minimizing looping of messages during routing table update are presented.
Hierarchical vehicle routing problems
Authors: Marchetti Spaccamela A. , Rinnooy Kan A. H. G. , Stougie L. 
Published: May 2007

AbstractHierarchical vehicle routing problems, in which the decision to acquire a number of vehicles has to be based on imperfect (probabilistic) information about the location of future customers, allow a natural formulation as two‐stage stochastic programming problems, where the objective is to minimize the sum of the acquisition cost and the length of the longest route assigned to any vehicle. For several versions of this difficult optimization problem, we show that simple heuristics have strong properties of asymptotically optimal behavior.
Properties of the k‐centra in a tree network
Authors: Andreatta G. , Mason F. M. 
Published: May 2007

AbstractThe k‐centrum of a graph G ‐ (V, E)is the set of vertices each minimizing the sum of the distances from it to the corresponding k farthest vertices of G. In this article properties of k‐centrum of trees, where edges have positive real lengths, are investigated.
Network reliability analysis using 2‐connected digraph reductions
Authors: Agrawal Avinash , Satyanarayana A. 
Published: May 2007

AbstractThe problem of computing the SKT reliability, the probability that a source s can send communication to a specified set of terminals K ⊂ V in a probabilistic digraph D = (V,E) is considered. For general digraphs, this problem is known to be NP‐hard and it is helpful to consider schemes that can decompose the problem into a number of smaller problems. A non‐separable digraph is 2‐connected if it contains a separation pair, a pair of nodes whose removal disconnects the digraph. Such a digraph can be partitioned into two or more segments. It is shown that at least one of these segments can be replaced by a simpler structure; this replacement results in an exact reliability preserving reduction. The proposed reduction scheme is general and is applicable to all digraphs containing a separation pair; earlier methods could only handle special cases. For a class of digraphs, called BSP digraphs, such a reduction is always admissible and the SKT reliability can be computed in time O(∣E∣). A digraph is a BSP digraph if its underlying undirected graph is series‐parallel. A BSP digraph can be cyclic or acyclic. No polynomial‐time algorithms were previously known for this class of digraphs.
Optimal consecutive‐2 systems of lines and cycles
Authors: Du D. Z. , Hwang F. K. 
Published: May 2007

AbstractA consecutive‐2 system is a graph where each vertex can either work or fail and the system fails if and only if two vertices incident to the same edge both fail. The simplest probability structure attached to such systems is to assume that vertex i has probability pi of failing and the states of the vertices are stochastically independent. For a given graph G of n vertices and a given set P of n probabilities, an optimal consecutive‐2 system is the triple (G,P,M), where M is a mapping from P to the vertices of G such that the probability of the system failing is minimum. Consecutive‐2 systems have been widely studied when the graph is either a line or a cycle. In this paper we study optimal consecutive‐2 systems which consist of many lines or many cycles. Our results provide optimal mappings that depend only on the rankings of the individual failure probabilities and not on their actual values. Moreover, we show by examples that rankings alone are probably insufficient to solve cases more complex than those solved in this paper.
A heuristic circulation‐network approach to solve the multi‐traveling salesman problem
Authors: Garcia‐Diaz Alberto 
Published: May 2007

AbstractThe overall methodology developed in this paper can be organized into two major parts. The first part consists of a representation of the Multi‐Traveling Salesman Problem as a network circulation model. The second part is a subtour elimination procedure. The circulation‐network representation of the Multi‐Traveling Salesman Problem allows the generation of a starting solution which satisfies the optimality LP conditions of the network, but which may not be feasible in the context of the original problem due to the existence of subtours. The proposed network algorithm iteratively reduces the set of solutions with subtours by eliminating one link and then rerouting its flow, using the remaining arcs without violating their LP optimality conditions. Computational results based on a sample of 91 randomly generated problems are reported.
On a conjecture of trietsch and handler on the flow‐dependent steiner ratio
Authors: Du D. Z. , Hwang F. K. 
Published: May 2007

AbstractRecently Trietsch and Handler extended a conjecture of Pollak and Gilbert on the Steiner ratio to a model first studied by Gilbert where the cost of an edge is flow dependent. For three given points Trietsch and Handler showed that the maximum Steiner ratio is achieved when the cost is independent of the flow, i. e., the extended conjecture is reduced to the original conjecture. They also conjectured that the two conjectures are equivalent for any number of given points. In this paper we give a counterexample to their conjecture if the number of given points is at least four. We also replace their proof for the three‐point case, which depends heavily on computer‐aided calculations, by a simple geometric proof.
The structure of distances in networks
Authors: Howe Eric , Johnson Charles R. , Lawrence James 
Published: May 2007

AbstractPart of this work is concerned with determining those graphs that produce extreme rays of the cone of shortest distance matrices of undirected linear n‐vertex graphs without loops. For n ≤ 4, for example, all extreme rays come from a certain class of “elementary” graphs, but for n ≥ 5 there are nonelementary extreme rays, and these are studied further. Another part of this work is concerned with the representation of a distance matrix as a set of distances among points in a normed vector space. The set of graphs (distance matrices) representable by a given norm and the set of norms (and dimensions of spaces) by which a given graph may be represented are studied. It is shown that lx is unique among lp norms in that any graph is lx representable in Rn−1. The l1 representable distance matrices are found to be just those in the cone generated by elementaries for all n. Other results on distance matrices are also included.
Reliable broadcast protocols in unreliable networks
Authors: Awerbuch Baruch , Event Shilmon 
Published: May 2007

AbstractBroadcast is the task of delivering copies of a packet to all nodes in a communication network. A broadcast is called reliable if all the packets are accepted by all the nodes in finite time and in the correct order. This paper presents a class of reliable broadcast protocols for unreliable networks. One of these protocols achieves reliable broadcast with minimum broadcast cost, assuming that the network allows reliable broadcast at all. In case that the network's topology is stable, the minimum broadcast delay is achieved. No existing broadcast protocol achieves this goal. As a by‐product, we achieve a new reliable routing protocol.
New lower planes for the network design problem
Authors: Ahuja R. K. , Murty V. V. S. 
Published: May 2007

AbstractA lower plane for the network design problem is a linear lower approximation of the objective function and is used to obtain a lower bound in the branch and bound algorithm. In this article, we derive two new lower planes for the network design problems through combinatorial arguments. The first lower plane is of complexity O(n4) and produces a lower bound which is sharper than those of existing lower planes. The second lower plane is of complexity O(n3) and produces a reasonably good lower bound. Computational results are presented comparing the bounds obtained by the new lower planes with those of the existing lower planes.
A quasi‐assignment algorithm for bus scheduling
Authors: Paixão J. Pinto , Branco I. M. 
Published: May 2007

AbstractA new and much faster algorithm is presented for the problem of assigning buses to a large number of short trips in an urban area. The trips are grouped into chains, beginning and ending at the same bus depot, and a vehicle is assigned to each one of them. Fleet size costs and dead heading time are to be minimized. This problem has been already formulated as a transportation problem and more recently, as an assignment model. However, some difficulties, such as the zero pivot phenomenon, rising in many practical cases drastically affected computing times required to obtain the optimal solution. This is overcome by an algorithm based on the hungarian method and making full use of the sparsity of the assignment matrix for the bus scheduling problem. Computational results comparing the different methods are given in the last section of the paper. Significant reductions in computing time are obtained for either real case applications or random generated test problems.
Computing k‐shortest path lengths in euclidean networks
Authors: Skiscim Christopher C. , Golden Bruce L. 
Published: May 2007

AbstractIn this paper, we examine the problem of finding k‐shortest paths between an origin and destination pair when distances are Euclidean. Two versions of a generalized Dijkstra algorithm are compared. Computational results show that the advantage of the adaptive version (measured by total number of permanent labels) grows with both k and the network size. For large networks, the adaptive algorithm exhibits a 100:1 advantage in the number of permanent labels set.
Bounding all‐terminal reliability in computer networks
Authors: Colbourn Charles J. , Harms Daryl D. 
Published: May 2007

AbstractMany bounds for the all‐terminal reliability of computer networks have been proposed. Of those computable in polynomial time, the Ball‐Provan bounds and the Lomonosov Polesskii bounds provide the tightest estimates. A strategy is developed here using linear programming to obtain bounds which are tighter than both the Lomonosov‐Polesskii and the Ball‐Provan bounds. Computational results on these new bounds are also reported.
Convexity and the Steiner tree problem
Authors: Scott Provan J. 
Published: May 2007

AbstractWe investigate the role convexity plays in the efficient solution to the Steiner tree problem. In general terms, we show that a Steiner tree problem is always computationally easier to solve when the points to be connected lie on the boundary of a “convex” region. For the Steiner tree problem on graphs and the rectilinear Steiner tree problem, we give definitions of “convexity” for which this condition is sufficient to allow a polynomial algorithm for finding the optimal Steiner tree. For the classical Steiner tree problem, we show that for the standard definition of convexity, this condition is sufficient to allow a fully polynomial approximation scheme.
Planarity testing of doubly periodic infinite graphs
Authors: Iwano Kazuo , Steiglitz Kenneth 
Published: May 2007

AbstractThis paper describes an efficient way to test the VAP‐free (Vertex Accumulation Point free) planarity of one‐ and two‐dimensional dynamic graphs. Dynamic graphs are infinite graphs consisting of an infinite number of basic cells connected regularly according to labels in a finite graph called a static graph. Dynamic graphs arize in the design of highly regular VLSI circuits, such as systolic arrays and digital signal processing chips. We show that VAP‐free planarity testing of dynamic graphs can be done efficiently by making use of their regularity. First, we will establish necessary conditions for VAP‐free planarity of dynamic graphs. Then we show the existence of a small finite graph which is planar if and only if the original dynamic graph is VAP‐free planar. From this it follows that VAP‐free planarity testing of one‐ and two‐dimensional dynamic graphs is asymptomically no more difficult than planarity testing of finite graphs, and thus can be done in linear time.
Hemoglobin depletion from red blood cell cytosol reveals new proteins in 2‐D gel‐based proteomics study
Authors: Bhattacharya Dipankar , Mukhopadhyay Debashis , Chakrabarti Abhijit 
Published: May 2007

AbstractProteomics studies to identify proteins in the erythrocyte cytosol have been largely affected by the huge abundance of hemoglobin (Hb), which masks the detection of other proteins in the 2‐D gel‐based separation. We have depleted Hb effectively from erythrocyte cytosol using cation exchange chromatography and have detected more than 600 protein spots in the Hb depleted hemolysate using 2‐DE. We have so far identified 59 proteins in the Hb‐depleted cytosol of normal erythrocytes, including 10 proteins not identified before.