bluuebunny/crossref_metadata_2025 huggingface dataset:
An advanced dual incremental network algorithm
Authors: Schmidt Stephen R. , Jensen Paul A. , Barnes J. Wesley
Published: May 2007

An extensive literature survey reveals that computational analyses of pure minimumcost‐network algorithms do not address the use of dual incremental codes. Previous studies only compare dual‐arc‐infeasible‐, primal‐dual‐, and primal‐type network codes. Of these three types, the primal method has been shown to be computationally superior to the other methods. This paper surveys the historical development of the dual incremental method up to and including the code DUALINC. Following a comprehensive description of DUALINC, a computational comparison is made with three other recently publicized codes, two primal codes and a dual‐arc‐infeasible code. The results of this comparison reveal that the new dual incremental code is much more efficient than the dual‐arc‐infeasible code and that it is competitive with the primal codes.
Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching
Authors: Reingold Edward M. , Supowit Kenneth J.
Published: May 2007

The expected costs of the matchings found by various divide‐and‐conquer heuristic algorithms are calculated, under the assumption that the vertices to be matched are uniformly distributed in the unit square. The expected times of the algorithms are calculated as well.
Heuristics for planar minimum‐weight perfect metchings
Authors: Iri Masao , Murota Kazuo , Matsui Shouichi
Published: May 2007

Several linear‐time approximation algorithms for the minimum‐weight perfect matching in a plane are proposed, and their worst‐ and average‐case behaviors are analyzed theoretically as well as experimentally. A linear‐time approximation algorithm, named the “spiral‐rack algorithm (with preprocess and with tour),” is recommended for practical purposes. This algorithm is successfully applied to the drawing of road maps such as that of the Tokyo city area.
Activity selection games and the minimum‐cut problem
Authors: Topkis Donald M.
Published: May 2007

The connection between the minimum‐cut problem in a capacitated network and certain combinatorial problems is well‐known. This article presents and analyzes a selection problem in the context of a cooperative game, with emphasis on the key role of associated minimum‐cut problems. Each coalition selects economic activities from private activities available to its members and public activities available to all coalitions. For each coalition, a minimum‐cut problem finds an optimal selection and the value of the characteristic function. The game is a convex game. Applying the Greedy Algorithm involves solving n minimum‐cut problems, where n is the number of players. The solution of n minimum‐cut problem determines whether a proposed payoff vector is in the core. An optimal selection of activities varies monotonically with the coalition membership and with the value of each activity. The Shapley value and each extreme point of the core vary monotonically with the value of each activity.
Ranking the vertices of a weighted digraph using the length of forward arcs
Authors: Kano Mikio , Sakamoto Akio
Published: May 2007

Let D = (V, A) be a weighted digraph with vertex set V and arc set A, and let α be a one‐to‐one mapping from V onto the set of integers {1, 2, …, |V|}. A mapping α is called a ranking of D. According to a ranking α, the arc set A is naturally partitioned into the set of forward arcs of α and that of backward ones. By using these subsets of rankings, we define three kinds of optimal rankings: forward optimal rankings, backward optimal rankings, and mutual optimal rankings. Since many results on the backward optimal rankings are already known, we mainly discuss the properties of the forward optimal rankings and the mutual ones in the present article.
Construction of centered shortest‐path trees in networks
Authors: Wall David W. , Owicki Susan
Published: May 2007

Many researchers in the area of distributed networks have found it convenient to assume the existence of a facility for routing broadcast messages to all the nodes in the network. We are investigating an approach called center‐based forwarding which routes messages via the branches of the shortest‐path tree for some node near the center of the network. In this article we show that this approach results in broadcasts that finish with low delay; we then explain how to construct centered trees in a loosely coupled network environment.
Radial location theory
Authors: Minieka Edward
Published: May 2007

This article presents algorithms to locate optimally a service facility in a network subject to the condition that the facility has only a specified radius over which it can serve.
Calculating bounds on reachability and connectedness in stochastic networks
Authors: Ball Michael O. , Provan J. Scott
Published: May 2007

In this article, computational procedures are presented for generating bounds on measures of network reliability. The two measures considered, reachability and connectedness, are the probability that there is an operating path from a node to all other nodes in a directed (respectively undirected) stochastic network. Our bounds, which are given in terms of polynomials in p, the common arc failure probability, are based on recent bounding results developed by the authors for the class of shellable independence systems. Two pairs of bounds are given: weaker bounds whose computation time is bounded by a polynomial in the size of the network and tighter bounds whose computation time is bounded by a polynomial in the size of the network and the number of minimum‐cardinality network cuts. Computational results are also given which evaluate the quality of the bounds. The generation of the bounds involves several interesting path and cut counting problems.
Shortest chain subject to side constraints
Authors: Aneja Y. P. , Aggarwal V. , Nair K. P. K.
Published: May 2007

Certain properties of a shortest chain subject to several side constraints are established. Based on these an implicit enumeration algorithm, that is, a generalization of the one given by Dijkstra for the case without any side constraint, is presented. Validation of the algorithm and an illustrative example are included.
Conditional connectivity
Authors: Harary Frank
Published: May 2007

For a noncomplete graph G, the traditional definition of its connectivity is the minimum number of points whose removal results in a disconnected subgraph with components H1,…,Hk. The conditional connectivity of G with respect to some graph‐theoretic property P is the smallest cardinality of a set S of points, if any, such that every component Hi of the disconnected graph G ‐ S has property P. A survey of promising properties P is presented. Questions for various P‐connectivities are listed in analogy with known results on connectivity and line‐connectivity.
An algorithm for constructing edge‐trees from hypergraphs
Authors: Gavril Fǎnicǎ , Tamari Robert
Published: May 2007

Consider a hypergraph H = (E, P) where E denotes the set of vertices and P the set of edges. The hypergraph H = (E, P) is called an edge‐tree hypergraph if there exists a tree T with edge set E such that every p = P is a path in T. We describe a polynomial time algorithm for deciding whether a given hypergraph H = (E, P) is an edge‐tree hypergraph. The algorithm can be used to decide whether a binary matroid is graphic or not.
Lower planes for the network design problem
Authors: Gallo G.
Published: May 2007

A new class of relaxations for the network design problem based on lower planes, i.e., linear lower approximations of the objective function, is introduced. Such relaxations provide lower bounds much sharper than the bounds used so far in branch and bound algorithms for this problem.
A Newton method for convex separable network flow problems
Authors: Klincewicz John G.
Published: May 2007

Previous feasible direction algorithms for convex, separable network flow problems that have appeared in the literature have all been linearly convergent. In this paper we propose an approximate implementation of the quadratically convergent Newton algorithm. The key to this implementation is a conjugate direction method that determines second‐order dual multiplier estimates at each iteration. This method exploits the network structure in a way that allows certain crucial matrix‐vector products to be computed in a simple pass through the arcs. Since this novel approach requires no matrix storage to compute these products, the algorithm can be used for large‐scale problems. Some computational experience with this new algorithm is reported.
Reductions to 1–matching polyhedra
Authors: Aráoz Julian , Cunningham William H. , Edmonds Jack , Green‐Krótki Jan
Published: May 2007

The matching polyhedron theorem of Edmonds and Johnson, which gives the convex hull of capacitated perfect b‐matchings of a bidirected graph, is proved by reducing this matching problem to the ordinary perfect 1–matching problem, for which there exists a short inductive proof of the corresponding polyhedral theorem. The proof method makes it possible to deduce nestedness and discreteness properties of optimal dual solutions to the general matching problem from analogous properties of optimal dual solutions to the perfect 1–matching problem. In particular, the total dual half‐integrality of the inequality system for general matching is shown to follow from that for 1–matching. Applications considered include determining the convex hull of unions of disjoint circuits of a graph.
Computational study of an improved shortest path algorithm
Authors: Glover Fred , Glover Randy , Klingman Darwin
Published: May 2007

Shortest and/or longest path analysis is a major analytical component of quantitative models used by transportation planners. The importance of shortest path analysis in all phases of transportation planning has given rise to intensive research and software development over the last three decades for solving shortest path problems. This paper presents a new hybrid solution algorithm called THRESH, which integrates the features of label setting and label correcting algorithms, yet appears to have performance characteristics that transcend both. Preliminary computational results indicate that it is substantially more efficient than the methods determined to be best by previous studies.
Vulnerability of communication networks
Authors: Caccetta Louis
Published: May 2007

Boesch, Harary, and Kabell recently introduced two measures of network vulnerability. They defined the persistence (edge persistence) of a graph as the minimum number of vertices (edges) whose deletion increases the diameter. In their paper they posed questions relating the existence of graphs with a prescribed number of edges, number of vertices, diameter, and persistence (edge persistence). In this paper we consider this extremal problem.
Two exact algorithms for the distance‐constrained vehicle routing problem
Authors: Laporte Gilbert , Desrochers Martin , Nobert Yves
Published: May 2007

This paper considers a version of the vehicle routing problem in which all vehicles are identical and where the distance travelled by any vehicle may not exceed a prespecified upper bound. The problem is first formulated as an integer program which is solved by means of a constraint relaxation procedure. Two exact algorithms are developed: one based on Gomory cutting planes and one on branch and bound. Numerical results are reported.
On minimal‐node‐cost planar embeddings
Authors: Storer James A.
Published: May 2007

The problem of embedding an undirected graph on the planar grid is considered. Two common cost measures for this sort of problem are the area consumed by the embedding and the total length of edges in the embedding. This paper considers a third cost measure, called thenode cost measure, which is the total number of bends that are present along edges of the embedding. The node cost measure has applications to light or microwave circuits where it requires a separate device each time a corner is turned. In addition, this problem has limited applications to traditional circuit and VLSI layout. Although it is shown that finding a minimal node‐code embedding is in general an NP‐complete problem, three good approximation strategies are given along with worst‐case bounds on their performance; one of the strategies is shown to be nearly optimal for a large class of graphs.
Synthesis of directed multicommodity flow networks
Authors: Itai A. , Pradhan D. K.
Published: May 2007

A necessary condition for synthesis of multicommodity flow networks is derived. The feasible flow region of a multicommodity flow network is shown to be an antiblocking polyhedron with rational slopes. Also, it is established that this condition is sufficient for two‐commodity flow networks. A synthesis algorithm for two‐commodity flow networks is proposed. The size of the resulting networks is studied and for some regions it is shown to be pseudolinear; in the worst case the network found by the algorithm is optimal to within a constant factor.
Independent sets in random sparse graphs
Authors: Gazmuri Pedro G.
Published: May 2007

We consider the problem of finding maximum independent sets on sparse graphs. A probabilistic analysis of this problem is presented, with the main objective being to obtain asymptotic lower and upper bounds on the size of the optimal solution. If we let n be the number of nodes in the graph, we show that with probability tending to 1 as n /rightarrow /infty, this size lies between [D1n] and [D2n], where D1 and D2 are specific functions of the average degree of a node. The lower bound is obtained by examining the behavior of a simple algorithm for constructing independent sets. We then extend our results to the case of random sparse hypergraphs and obtain bounds using similar methods. Finally, we consider the case of Euclidean sparse graphs. Simple asymptotically optimal strategies are presented for this model.
Linearized simplicial decomposition methods for computing traffic equilibria on networks
Authors: Pang Jong‐Shi , Yu Chang‐Sung
Published: May 2007

This article discusses the solution of the fixed‐demand traffic equilibrium problem by certain linearized simplicial decomposition methods. These methods are derived from the family of linear approximation methods for solving a general variational inequality problem. The central idea of a linearized simplicial decomposition method is that instead of solving linear variational inequality subproblems over the entire set of feasible flows as in a typical linear approximation method, one solves the same subproblems over subsets of feasible flows where each such subset is defined explicitly by certain extreme points of the (polyhedral) set of feasible flows. A global convergence result of the linearized decomposition methods will be established under suitable assumptions on the change of the set of “working” extreme points in each iteration plus some standard conditions on the linear approximating mappings used. Extensive computational results with the use of such methods are reported. Sizes of problems solved range from relatively small to reasonably large.
Lagrangian dual coordinatewise maximization algorithm for network transportation problems with quadratic costs
Authors: Ohuchi Azuma , Kaji Ikuo
Published: May 2007

This paper gives the Lagrangian dual coordinatewise maximization (LDCM) algorithm for network transportation problems with strictly convex quadratic costs (NTPQ). An explicit expression for the dual function associated with NTPQ is obtained. Some properties of the dual function are shown. Then, using these properties, a procedure which involves successively maximizing the dual function with respect to each of its dual coordinates is applied to obtain the optimal dual solution. Then the optimal primal solution is obtained by substituting the dual solution to the simple expression. Computational results for 200 randomly generated problems reveal the effectiveness of the algorithm. The key idea of applying the Lagrangian dual method to NTPQ is that the objective function of the network problems is strictly convex. This strict convexity allows one to finesse problems that occur in using Lagrangian methods with more general problems. In particular, because the optimal solution of the Lagrangian problem is unique, the dual function is differentiable and an optimal solution to the Lagrangian with optimal multipliers is optimal in the original primal problem. These are strong results that are not true in general.
On the practical importance of asymptotic optimality in certain heuristic algorithms
Authors: Psaraftis Harilaos N.
Published: May 2007

This article presents an informal discussion of the issue of asymptotic optimality of heuristics from the viewpoint of the operations research practitioner. It is suggested that certain heuristics belonging to the above class are likely to perform questionably in practice, with regard both to relative error and to computational tractability. Possible explanations of this phenomenon are offered and suggestions for further research toward a better understanding of this problem are presented.
Lagrangian relaxation for the star‐star concentrator location problem: Approximation algorithm and bounds
Authors: Mirzaian Andranik
Published: May 2007

The star‐star concentrator location problem (SSCLP), which is a network layout problem, is considered. SSCLP is formulated as an integer linear programming problem. The Lagrangian relaxation (LR) method is used to obtain suboptimal solutions (upper bounds) and lower bounds. Three different LRs are used for SSCLP. The resulting Lagrangian dual problems are shown to be equivalent to some linear programming problems. An approximation algorithm is suggested for SSCLP that produces both a feasible solution (upper bound) and a lower bound. It is shown that if z and z̄are the lower and upper bounds found, then z̄/z ≤ k, where k is the concentrator capacity. Some computational examples with up to 50 terminals and 20 potential concentrator sites are considered. All the network designs obtained are shown to be within 2.8% of optimal.
The most reliable series‐parallel networks
Authors: Neufeld Eric M. , Colbourn Charles J.
Published: May 2007

The design of reliable communications networks is an interesting and important topic. Perhaps the most common measure of reliability is a probabilistic one: the probability that a network is connected given the possibility of statistically independent line failures. In general, this is not efficiently computable. In this article, we develop a formula for the reliability of the most reliable maximal series‐parallel networks. The most reliable maximal series‐parallel networks are those maximal series‐parallel networks with the minimum number of vertices of degree 2, independent of many of the simpler reliability estimates. A two‐dimensional recurrence relating networks of varying sizes and edge deficiencies provides a generating function which in turn is exploited to give a simple closed expression for reliability.
On digraphs with a rooted tree structure
Authors: Szwarcfiter Jayme L.
Published: May 2007

A special class of reducible digraphs is characterized, those whose transitive reduction of the associated dag is a directed rooted tree. Polynomial time algorithms are described for the problems of recognition, isomorphism and finding minimum equivalent digraphs of this class. An approximative algorithm is also given for the general case of this last problem. The size of the approximation is always less than twice the exact solution. In addition, isomorphism of depth first search is solved as a special case of isomorphism of this class.
A minimum concave‐cost dynamic network flow problem with an application to lot‐sizing
Authors: Graves Stephen C. , Orlin James B.
Published: May 2007

We consider a minimum‐cost dynamic network‐flow problem on a very special network. This network flow problem models an infinite‐horizon, lot‐sizing problem with deterministic demand and periodic data. We permit two different objectives: minimize long‐run average‐cost per period and minimize the discounted cost. In both cases we give polynomial algorithms when certain arc costs are fixed charge functions, and others are linear.
On the multiplication of divisions: The use of graphs for sports scheduling
Authors: de Werra D.
Published: May 2007

The construction of schedules for a sports league reduces to finding a factorization of a complete graph. In the case where all games are played in the home city of one of the teams, one can represent schedules by means of oriented edge colorings. In this article we consider the case where the league consists of several divisions of equal size; constructions are described which take into account requirements concerning the breaks in the alternating sequences of home and away games as well as the consecutive arrangements of games inside a division or between divisions.
Fault‐tolerant broadcast graphs
Authors: Liestman Arthur L.
Published: May 2007

Broadcasting refers to the process of information dissemination in a communications network whereby a message, originated by one member, is transmitted to all members of the network. By incorporating redundancy in the calling scheme, the completion of the broadcast may be guaranteed in the presence of up to k link failures. A k fault‐tolerant broadcast graph represents a network configuration which admits such a scheme. This article investigates these graphs and the tradeoff between the time allowed for broadcasting and the number of edges required in the graph.
The optimal location of a path or tree in a tree network
Authors: Minieka Edward
Published: May 2007

This article describes methods for finding an optimal location for a path‐shaped or tree‐shaped facility of a specified size in a tree network. Four optimization criteria are examined: minimizing distancesum, minimizing eccentricity, maximizing distancesum, and maximizing eccentricity. Solution algorithms are presented for all but one case.
Probabilistic analysis of a network design problem heuristic
Authors: Wong Richard T.
Published: May 2007

Previous work has shown the budget network design problem (selecting a subset of arcs, subject to a budget constraint, so that the total weighted sum of the shortest paths in the network is minimized) to be a very difficult optimization problem. This article gives an efficient heuristic procedure for solving budget network design problems embedded in a circle on the euclidean plane where the nodes are independently and randomly distributed over the circle. With mild conditions on the budget constraint, we prove that as the number of nodes increases, the probability that the heuristic solution value exceeds any fixed percentage of the optimal solution value goes to zero. Computational results for the heuristic arc given.
Algorithms for finding P‐centers on a weighted tree (for relatively small P)
Authors: Jeger M. , Kariv O.
Published: May 2007

Algorithms of O(p. n. log n) time to find an (absolute or vertex) p‐center on a weighted tree of n vertices are presented. Those algorithms represent improvement over previous known results in the range p < log n (for the vertex p‐center problem) and in the range p < log n. log log n (for the absolute p‐center problem).
Component‐level redundancy is better than system‐level redundancy for channel graphs
Authors: Hwang F. K. , Shepp L. A.
Published: May 2007

A well known engineering principle in introducing redundancy to a system is that component‐level redundancy is better than system‐level redundancy. However, the mathematical demonstration of this principle is usually for coherent systems constructed by one sequential synthesis and one parallel synthesis (the proof consists of showing that the parallel synthesis should be at the component level). In this article we demonstrate the same principle for systems constructed by parallel‐sequential‐parallel synthesis, one parallel synthesis at the component level and one at the system level. We show that the parallel synthesis at the component level should have more redundancy. The particular vehicle we use for this demonstration is the comparison of blocking probabilities for a 2‐port network known as channel graphs. The crux of the mathematical demonstration is the lemma that [1 − Π (1 − P)]1/a decreases in a, 0 ≤ pi ≤ 1, i = 1,…, n.
On node constraint networks
Authors: Gröflin Heinz
Published: May 2007

We give node constraint versions of the circulation theorem and max flow‐min cut and min flow‐max cut theorems, and show how they provide a short and elementary treatment of the problems of finding in a poset an optimum antichain or an optimum convex set.
Strongly connected orientations of mixed multigraphs
Authors: Chung Fan R. K. , Garey Michael R. , Tarjan Robert E.
Published: May 2007

We study the problem of orienting all the undirected edges of a mixed multigraph so as to preserve reachability. Extending work by Robbins and by Boesch and Tindell, we develop a linear‐time algorithm to test whether there is an orientation that preserves strong connectivity and to construct such an orientation whenever possible. This algorithm makes no attempt to minimize distances in the resulting directed graph, and indeed the maximum distance, for example, can blow up by a factor proportional to the number of vertices in the graph. Extending work by Chvátal and Thomassen, we then prove that, if a mixed multigraph of radius r has any strongly connected orientation, it must have an orientation of radius at most 42 + Ar. The proof gives a polynomial‐time algorithm for constructing such an orientation.
Integer flows in network with fuzzy capacity constraints
Authors: Chanas Stefan , Kolodziejczyk Waldemar
Published: May 2007

A generalization of the maximum flow problem in a network with one‐sided (upper) and two sided constraints on arc capacities is presented. It allows for violating the capacity constraints in some ranges of tolerance. To solve the generalized problem the apparatus of the fuzzy set theory is used. The efficient algorithms are developed for integer flows.
Incorporating dependent node damage in deterministic connectivity analysis and synthesis of networks
Authors: Heffes H. , Kumar A.
Published: May 2007

Survivability of a node vulnerable network is often assessed in terms of the (node) connectivity of the graph that represents the logical topology of the network. When the damage causing events have widespread impact then, owing to the physical layout of the network facilities, each event can destroy several nodes. As a survivability measure, therefore, we define the generalized connectivity as the minimum number of events (rather than the minimum number of node removals) required to disconnect the network. To model the possible effects of damage causing events, we introduce the notion of a dependence graph on the nodes of the network and a set of admissible cliques in this graph. Nodes that are nonadjacent in the dependence graph are independent, i. e., they cannot be damaged by the same event, and each event destroys an admissible clique of nodes. We present techniques for calculating or bounding the generalized connectivity of given network graphs, and for synthesizing minimum link networks with prescribed generalized connectivity.
Implementation of algorithms for K shortest loopless paths
Authors: Perko Aarni
Published: May 2007

Implementations of loopless k shortest path algorithms are examined. Efficient storage structures for a large number of paths are given. A fast algorithm for determining the shortest paths in Yen's method is developed. Timing experiments show that a hybrid of Clarke's and Yen's methods is generally the fastest, although not significantly. Using upper bounds for the lengths of paths essentially improves all methods.
Minisum location of a traveling salesman
Authors: Berman O. , Levi D. Simchi
Published: May 2007

In this article we deal with the problem of locating on a network a service unit that must visit all the calls that are registered in a service list. Each node can generate a call with a given probability and the service list contains the first b calls that have arrived b ≤ n (n is the number of nodes). In our problem the optimal location minimizes the expected length of a traveling salesman tour (TST) traveled. For the problem (which requires 2n calculations of probabilities), we develop an O(n) Algorithm when b = n. for a tree, and study the sensitivity of this optimal solution when b < n.
On the number of active nodes in a multicomputer system
Authors: Barak Amnon , Drezner Zvi , Gurevich Yuri
Published: May 2007

In this article we develop probabilistic algorithms for estimating the number of active nodes in a multicomputer system which consists of independent computers that are interconnected by a communication network. The algorithms are based on routine exchange of messages among the nodes of the multicomputer, using random routing. We show that each active node can find an ϵ‐estimate of the fraction λ of active nodes in the system in time that depends only on ϵ and λ. The underlying approach can be used for finding various global properties of distributed systems with decentralized control.
First‐and second‐order bounds on terminal reliability
Authors: Assous J. Yael
Published: May 2007

We show that existing network algorithms solve the terminal reliability bound problem under limited information about the probabilities of operation of the components. Tightening of the bounds is achieved by introducing bounds on the probabilities that pairs of network components fail. A heuristic algorithm is developed to determine a tighter lower bound. The problem of the upper bound is also addressed. Our approach discards the traditional assumption of statistical independence of components' failures.
The minimum dummy task problem
Authors: Spinrad Jeremy
Published: May 2007

The minimum dummy task problem for PERT networks is NP‐complete on arbitrary graphs. This paper presents a very simple heuristic algorithm for the minimum dummy task problem and proves that this algorithm finds an optimal PERT network for various classes of graphs, including interval orders, two‐dimensional partial orders, and seriesparallel partial orders.
An approximation algorithm for the maximum independent set problem in cubic planar graphs
Authors: Choukhmane Elarbi , Franco John
Published: May 2007

A polynomial time approximation algorithm A for the problem of finding a maximal independent set for cubic planar graphs is presented. It is shown that MA > 6/7 in the case of cubic planar graphs and MA = 7/8 in the case of triangle free cubic planar graphs where MA is the worst‐case ratio of the size of the independent set found by A to the size of the maximum independent set for the graph input to A.
Efficient points on a network
Authors: Hansen Pierre , Thisse Jacques‐Françols , Wendell Richard E.
Published: May 2007

Properties of efficient points on a network are given. They are then used to devise (i) a linear algorithm for efficient points on a tree, (ii) on O(m log n) algorithm for the set of links common to all shortest paths between two points, and (iii) a polynomial algorithm for efficient points on a general network.
Improving reliability bounds in computer networks
Authors: Brecht Timothy B. , Colbourn Charles J.
Published: May 2007

The probability that a computer network is operational in an environment of statistically independent link failures has been widely studied. Three natural problems arise, when all nodes are to be connected (all‐terminal reliability), when two nodes are to communicate (2‐terminal reliability), and when k specified nodes are to communicate (k‐terminal reliability); the latter case includes the first two. Each of these reliability measures is NP‐hard to compute, and thus efficiently computable reliability bounds are of significant interest. To date, the all‐terminal and 2‐terminal cases have been treated separately, and few results apply to the k‐terminal case. In this paper, we develop a simple strategy to obtain k‐terminal reliability bounds. In the process, we demonstrate improvements on the previous best bounds for all‐terminal, k‐terminal, and 2‐terminal reliability. Computational experience with these new bounds is reported, by comparing the new lower bounds to existing lower bounds.
Domination and location in acyclic graphs
Authors: Slater Peter J.
Published: May 2007

Locating‐dominating sets are of interest in safeguard applications of graphical models of facilities. A subset S of the vertex set V of a graph G is a dominating set if each vertex u ϵ V ‐ S is adjacent to at least one vertex in S. For each v in V ‐ S let S(v) denote the set of vertices in S which are adjacent to v. A dominating set S is defined to be “locating” if for any two vertices v and w in V ‐ S one has S(v) ≠ S(w). Sharp bounds on the cardinality of locating‐dominating sets for arbitrary graphs on p vertices and for trees on p vertices are given, and a linear (that is O(P)) algorithm for finding a minimum cardinality locating‐dominating set in an acyclic graph is presented.
Investing in arcs in a network to maximize the expected max flow
Authors: Wallace Stein W.
Published: May 2007

Consider a network with arcs subject to failures. We show how the problem of investing in new arcs in such a network in order to increase the expected max flow as much as possible can be formulated as a stochastic program with network recourse. We show how to decompose the problem, and consider both exact methods and approximations. Convergence proofs are given. We demonstrate that max flow recourse problems can be solved very efficiently, since lower and upper bounds are equally simple to evaluate.
Forbidden subgraphs and graph decomposition
Authors: Wagner Donald K.
Published: May 2007

Series‐parallel graphs, outerplanar graphs, and graphs whose polygon matroids are transversal have been characterized by forbidden subgraphs. Tutte introduced a graph decomposition for nonseparable graphs. The results of this paper relate the existence of the forbidden subgraphs to properties of the decomposition. Algorithmic implications are considered.
On the properties of directed switching networks
Authors: Wu Min‐You , Chan Shu‐Park
Published: May 2007

The theory of directed switching networks is developed. After the fundamental concepts are defined, the rank of the path matrix of a Directed Single‐Contact (Di‐SC) network is discussed. The theorem which gives the essential relationship between the SC and Di‐SC networks is proved. Then the Odd‐Addition‐Subtraction (OAS) condition is given as a necessary condition for Di‐SC functions. The analysis of directed switching networks and the synthesis of Di‐SC networks are also given for practical applications. The results could be used in the design of electrical and computer systems with directed elements.
On some matching problems arising in vehicle scheduling models
Authors: Bertossi A. A. , Carraresi P. , Gallo G.
Published: May 2007

Two bipartite matching problems arising in Vehicle Scheduling are considered: the capacitated matching and the multicommodity matching. For the former, given a reasonable cost structure, we can exhibit a polynomial time algorithm, while the general case is conjectured to be NP‐hard. The latter problem is shown to be NP‐hard. A heuristic algorithm based on Lagrangean relaxation for the capacitated version of the multicommodity matching is also presented together with experimental results.
Digraphs with maximum number of paths and cycles
Authors: Perl Yehoshua
Published: May 2007

We construct a digraph with the maximum number of simple paths between two specified vertices, for a digraph with a given number of edges. The following cases are considered: digraphs with parallel edges, acyclic simple digraphs and general simple digraphs. The corresponding extremal digraphs are the tri‐chains, the (deficient) Fibonacci digraphs and (if our conjecture is true) the 3‐diamond strings, respectively. The similarity of these three families of digraphs is discussed. The related problem of digraphs with the maximum number of simple cycles for a given number of edges is considered too.
Data transfers in networks with transceivers
Authors: Choi Hyeong‐Ah , Hakimi S. Louis
Published: May 2007

The scheduling of data transfers in networks, where the schedule does not permit interruption and each communication module can be used as a transmitter and as a receiver (i.e., as a transceiver) was studied by Coffman et al. The same problem when interruption in the schedule is permitted and the transmitting and receiving modules are distinct was studied by Choi and Hakimi among others. Hajek and Sasaki studied another interesting variation of the problem where interruption is permitted but each communication module is a transmitter and a receiver. This paper presents certain generalizations and improvements of Hajek and Sasaki's results.
Algorithms for maximum k‐colorings and k‐coverings of transitive graphs
Authors: Gavril Fǎnicǎ
Published: May 2007

Consider a graph G and a positive integer k. The maximum k‐coloring problem is to color a maximum number of vertices using k colors, such that no two adjacent vertices have the same color. The maximum k‐covering problem is to find k disjoint cliques covering a maximum number of vertices. The present paper contains polynomial time algorithms for finding maximum k‐colorings and maximum k‐coverings of transitive graphs.
Probabilistic analysis of the longest hamiltonian tour problem
Authors: Vohra Rakesh V.
Published: May 2007

In this paper we study the probabilistic behavior of the farthest neighbor heuristic for finding the longest Hamiltonian tour in a graph. We assume the edge weights are independent random variables uniformly distributed in [0,1]. If F, is the length of the heuristic tour and L, the optimal tour then Fn/Ln → 1 a.s. as n → α. We also show that Ln/n → 1 a.s. as n → ∞.
On a property of cyclic covers of p‐graphs
Authors: Politof Themistocles
Published: May 2007

A directed graph G with a source s and a sink t is called a p‐graph if every edge of G belongs to an elementary (s,t)‐path of G. If C is a cycle of the p‐graph G then a cyclic cover of C is a set of (s,t)‐paths of G that contains all the edges of C. A cyclic cover Q is minimal if for every path P e Q, Q = {P} is not a cover of C. The following property is known and was used in providing an important result in network reliability: A cyclic p‐graph has a cycle C and a path P such that P is not contained in any minimal cover of C. In this note we give a simpler proof of this property which provides more insight into the nature of cyclic covers in p‐graphs.
A single‐server priority queueing‐location model
Authors: Batta Rajan , Larson Richard C. , Odoni Amedeo R.
Published: May 2007

This paper considers the problem of locating a single server on a network, relaxing the assumption that the server is always available for service, and explicitly accounting for queueing. The resulting queueing‐location model allows for an arbitrary number of priority classes. Properties of the objective function are developed and algorithms presented for obtaining the optimal location on tree and cyclic networks. Sensitivity analysis with respect to the average arrival rate of calls is investigated. A numerical example is presented to illustrate the results of this paper. The major conclusions of the paper include: (a) the optimal location need not be at a node of the network, (b) the optimal location changes as a function of the arrival rate of calls into the system, (c) the optimal location is usually different from that obtained by grouping all calls into one priority class.
Vertex domination‐critical graphs
Authors: Brigham Robert C. , Chinn Phyllis Z. , Dutton Ronald D.
Published: May 2007

A dominating set in a graph G is a set of vertices D such that every vertex of G is either in D or is adjacent some vertex of D. The domination number Γ(G) of G is the minimum cardinality of any dominating set. A graph is vertex domination‐critical if the removal of any vertex decreases its domination number. This paper gives examples and properties of vertex domination‐critical graphs, presents a method of constructing them, and poses some open questions. In the process several results for arbitrary graphs are presented.
Contribution of laser microdissection‐based technology to proteomic analysis in hepatocellular carcinoma developing on cirrhosis
Authors: Dos Santos Alexandre , Thiers Valérie , Sar Sokhavuth , Derian Nicolas , Bensalem Noura , Yilmaz Funda , Bralet Marie‐Pierre , Ducot Béatrice , Bréchot Christian , Demaugre France
Published: May 2007

Hepatocellular carcinoma (HCC) is a major cause of cancer worldwide. Proteomic studies provide opportunities to uncover targets for the diagnosis and treatment of this disease. However, in HCC developing in a setting of cirrhosis, the detection of proteome alterations may be hampered by the increased cellular heterogeneity of tissue when analysing global liver homogenates. The aim of this study was to evaluate whether the identification of proteome alterations in these HCC cases was improved when the differential protein profile between tumour and non‐tumour areas of liver was determined using hepatocytes isolated by laser microdissection (LM). Differential profiles established with LM‐hepatocytes and liver section homogenates using 2‐DE and MS exhibited noticeable differences: 30% of the protein spots with deregulated expression in tumorous LM‐samples did not display any modification in homogenates; conversely 15% of proteins altered in tumorous homogenates were not impaired in LM‐hepatocytes. These alterations resulted from the presence in cirrhotic liver of fibrotic stroma which displayed a protein pattern different from that determined in LM‐hepatocytes. In conclusion, our data demonstrate the interest of LM in distinguishing between fibrotic and hepatocyte proteome alterations and thus the benefit of LM to proteome studies of HCC developing in a context of cirrhosis.
Black hole entropy function and attractor equations
Authors: Lopes Cardoso G.
Published: May 2007

The macroscopic entropy and the attractor equations for extremal black hole solutions follow from a variational principle based on an entropy function. We review this variational principle for static extremal black holes in four space‐time dimensions and we discuss an example in the context of N = 2 supergravity.
Non‐linear realizations, super branes and kappa symmetry
Authors: Gomis J. , Kamimura K. , West P.
Published: May 2007

We will show how the theory of non‐linear realizations can be used to naturally incorporate kappa transformations for the superpoint particle. Similar results also hold for a general super p‐brane, however we must in these cases include an additional Lorentz transformation.
Adding magnetic flux to the baryon vertex
Authors: Janssen B. , Lozano Y. , Rodríguez‐Gómez D.
Published: May 2007

We generalise the baryon vertex configuration of AdS/CFT by adding magnetic field on its worldvolume, dissolving D‐string charge. A careful analysis of the configuration shows that there is an upper bound on the number of dissolved strings. We provide a microscopical description of this configuration in terms of a dielectric effect for the dissolved strings.
Entropy of three‐charge black holes on a circle
Authors: Harmark T. , Kristjánsson K.R. , Obers N.A. , Rønne P.B.
Published: May 2007

We study phases of five‐dimensional three‐charge black holes with a circle in their transverse space. In particular, when the black hole is localized on the circle we compute the corrections to the metric and corresponding thermodynamics in the limit of small mass. When taking the near‐extremal limit, this gives the corrections to the finite entropy of the extremal three‐charge black hole as a function of the energy above extremality. For the partial extremal limit with two charges sent to infinity and one finite we show that the first correction to the entropy is in agreement with the microscopic entropy by taking into account that the number of branes shift as a consequence of the interactions across the transverse circle.
The Hagedorn temperature in a decoupled sector of AdS/CFT
Authors: Harmark T. , Kristjansson K. , Orselli M.
Published: May 2007

We match the Hagedorn/deconfinement temperature of planar 𝒩 = 4 super Yang‐Mills (SYM) on ℝ × S3 to the Hagedorn temperature of string theory on Ads5 × S5. The match is done in a near‐critical region where both gauge theory and string theory are weakly coupled. On the gauge theory side we are taking a decoupling limit found in [7] in which the physics of planar 𝒩 = 4 SYM is given exactly by the ferromagnetic XXX1/2 Heisenberg spin chain. We find moreover a general relation between the Hagedorn/deconfinement temperature and the thermodynamics of the Heisenberg spin chain. On the string theory side, we identify the dual limit which is taken of string theory on a maximally symmetric pp‐wave background with a flat direction, obtained from a Penrose limit of Ads5 × S5. We compute the Hagedorn temperature of the string theory and find agreement with the Hagedorn/deconfinement temperature computed on the gauge theory side. Finally, we discuss a modified decoupling limit in which planar 𝒩 = 4 SYM reduces to the XXX1/2 Heisenberg spin chain with an external magnetic field.
Supersymmetry and cosmic censorship
Authors: Ortín T.
Published: May 2007

We show that requiring unbroken supersymmetry everywhere in black‐hole‐type solutions of N = 2, d = 4 supergravity coupled to vector supermultiplets ensures in most cases absence of naked singularities. We show that the requirement of global supersymmetry implies the absence of sources for NUT charge, angular momentum, scalar hair and negative energy, for which there is no microscopic interpretation in String Theory. These conditions exclude, for instance, singular solutions such as the Kerr‐Newman with M = |q|, which fails to be everywhere supersymmetric. There are, nevertheless, everywhere supersymmetric solutions with global angular momentum and non‐trivial scalar fields. We also present similar preliminary results in N = 1, d = 5 supergravity coupled to vector multiplets.
Orientifolding in N = 2 superspace
Authors: Robles‐Llana D. , Roček M. , Saueressig F. , Theis U. , Vandoren S.
Published: May 2007

We discuss orientifold projections on superspace effective actions for hypermultiplets. We present a simple and new mechanism that allows one to find the Kähler potential and complex structure for the N = 1 theory directly in terms of the parent N = 2 theory. As an application, we demonstrate our method for Calabi‐Yau orientifold compactifications of type IIB superstrings.
Yangians in string theory and Yang‐Mills theory
Authors: Nappi C.R.
Published: May 2007

In recent years, higher loop integrability has been the object of much attention. An important part of that discourse is to check that the Yangian symmetry survives at higher loops. We offer a brief update of the progress in this area.
Probe D‐branes in superconformal field theories
Authors: Edelstein J.D.
Published: May 2007

We overview the main configurations of D‐brane probes in the AdS5 × X5 background of type IIB string theory (X5 being a Sasaki–Einstein manifold), and examine their most salient features from the point of view of the dual quiver superconformal field theory.
Parafermions, brane distributions and FRW hierarchies
Authors: Petropoulos P.M.
Published: May 2007

I review a class of exact string backgrounds, which appear in hierarchies, where the boundary of the target space of an exact sigma model is itself the target space of another exact model. From the worldsheet viewpoint this is due to the existence of (1,1) operators based on parafermions. From the target space side, it is reminiscent of the structure of maximally symmetric Friedmann–Robertson–Walker cosmological solutions, with broken homogeneity though. Cosmological evolution in this framework raises again the question of the nature of time in string theory.