bluuebunny/crossref_metadata_2025_split huggingface dataset:
Activity selection games and the minimum‐cut problem
Authors: Topkis Donald M. 
Published: May 2007

AbstractThe 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

AbstractLet 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

AbstractMany 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.
Calculating bounds on reachability and connectedness in stochastic networks
Authors: Ball Michael O. , Provan J. Scott 
Published: May 2007

AbstractIn 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

AbstractCertain 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

AbstractFor 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

AbstractConsider 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.
A Newton method for convex separable network flow problems
Authors: Klincewicz John G. 
Published: May 2007

AbstractPrevious 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

AbstractThe 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

AbstractShortest 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

AbstractBoesch, 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

AbstractThis 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

AbstractThe 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

AbstractA 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

AbstractWe 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

AbstractThis 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

AbstractThis 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

AbstractThis 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

AbstractThe 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

AbstractThe 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

AbstractA 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

AbstractWe 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

AbstractThe 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

AbstractBroadcasting 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

AbstractThis 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

AbstractPrevious 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

AbstractAlgorithms 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

AbstractA 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.
Strongly connected orientations of mixed multigraphs
Authors: Chung Fan R. K. , Garey Michael R. , Tarjan Robert E. 
Published: May 2007

AbstractWe 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

AbstractA 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.