bluuebunny/crossref_metadata_2025_split huggingface dataset:
A network recourse decomposition method for dynamic networks with random arc capacities
Authors: Powell Warren B. , Cheung Raymond K.‐M. 
Published: May 2007

AbstractWe study a class of two‐stage dynamic networks with random arc capacities where the decisions in the first stage must be made before realizing the random quantities in the second stage. The expected total cost of the second stage is a function of the first‐stage decisions, known as the expected recourse function, which is generally intractable. This paper proposes a new method to approximate the expected recourse function as a convex, separable function of the supplies to the second stage. First, the second‐stage network is decomposed using Lagrangian relaxation into tree subproblems whose expected recourse functions are numerically tractable. Subgradient optimization is then used to update the Lagrange multipliers to improve the approximations. Numerical experiments show that this structural decomposition approach can produce high‐quality approximations of the expected recourse functions for large stochastic networks. © 1994 by John Wiley & Sons, Inc.
Personnel shift assignment: Existence conditions and network models
Authors: van den Berg Yeroon , Panton David M. 
Published: May 2007

AbstractThe personnel scheduling problem is known to be a five‐stage process in which the final stage involves the assignment of shifts to the days worked in the schedule. This paper discusses the existence conditions for both continuous and forward rotating shift assignments and heuristic network algorithms for the determination of such assignments. Results generated for a number of test problems demonstrate, first, that the network devised to search for continuous solutions produces these solutions in a high proportion of cases where such solutions are known to exist. Second, for more general problems, the algorithm is shown to be efficient in its ability to generate either continuous or rotating solutions. © 1994 by John Wiley & Sons, Inc.
Experimental evaluation of a partitioning algorithm for the steiner tree problem in R2 and R3
Authors: Ravada Sivakumar , Sherman Alan T. 
Published: May 2007

AbstractWe experimentally evaluate sequential and distributed implementations of an approximation partitioning algorithm by Kalpakis and Sherman for the Geometric Steiner Minimum Tree Problem (GSMT) in Rd for d = 2,3. Our implementations incorporate an improved method for combining the subproblems, and single‐and double‐edge reduction techniques to eliminate unnecessary Steiner points created by the partitioning process. Results show that these refinements are crucial in practice to produce high‐quality results. Moreover, with these refinements, the partitioning algorithm is an effective practical heuristic, which in less time finds solutions roughly comparable with those computed by Smith's Algorithm. The partitioning algorithm depends on a parameter t through which the user can trade off time for solution quality. To solve each of the subproblems of size at most t, we apply Smith's Algorithm, the only other Steiner tree algorithm known for R3 under the Euclidean norm. Using uniformly generated point sets in the d‐cube [0, 100]d, we compare the running time and solution quality for the partitioning algorithm for various values of t against that of Smith's Algorithm applied to the entire input. We also estimate the constant factor in the 1 + O(t−1/d(d‐1)) asymptotic performance bound proven by Kalpakis and Sherman and find that it is less than one. With d = 2 on input sets of 25 points, our sequential implementation with t = 7 typically found within 6 seconds a Steiner tree within 1% of the cost (342) of that computed by Smith's Algorithm in 20 seconds. At t = 13 and using approximately 15 seconds, our sequential implementation typically found Steiner trees within 0.1% of this cost. Similarly, with d = 3 on input sets of 60 points, our distributed implementation with t = 10 typically found within 22 seconds a Steiner tree within 1% of the cost (1059) of that computed by Smith's Algorithm in 200 seconds. At t = 31 and using approximately 108 seconds, our distributed implementation usually found slightly better Steiner trees than did Smith's Algorithm. © 1994 by John Wiley & Sons, Inc.
Reliable distributed diagnosis for multiprocessor systems with random faults
Authors: Berman Piotr , Pelc Andrzej 
Published: May 2007

AbstractWe study a probabilistic setting for distributed fault diagnosis in multiprocessor systems. A system is an undirected graph with nodes representing processors and edges representing communication links. Processors are assumed to fail independently with some probability p. They test their neighbors, and a fault‐free processor has probability 1 − q of discovering a fault of a failed neighbor in an individual test. Subsequently, fault‐free processors attempt to diagnose all the processors of the system with communication based on the test results. During communication, the behavior of faulty processors may be arbitrary (socalled malicious). For every p ≤ ½, q ≤ 1, we construct systems with O(n log n) links in which distributed probabilistic diagnosis can be achieved with probability of correctness at least 1 − n−1. We also show that for some small fixed p and q a similar result holds for the hypercube. On the other hand, we prove that for sufficiently small k, for a system with n processors and kn log n links, the probability of achieving correct diagnosis cannot exceed n−0.5. © 1994 by John Wiley & Sons, Inc.
An exact lower bound on the number of cut‐sets in multigraphs
Authors: Harada Hideaki , Sun Zheng , Nagamochi Hiroshi 
Published: May 2007

AbstractA cut‐set in an undirected multigraph G is a subset of edges whose removal makes the graph disconnected. Let mi(G) denote the number of all cut‐sets, each of which consists of i edges. In this paper, for any multigraph G with n nodes and e (⩾3n/2) edges, we show that mi(G) with α ⩽ i ⩽ 2(α ‐ γ) ‐ 3, where α = ⌊2e/n⌋ and γ = ⌊2e/n(n ‐ 1)⌋, is greater than or equal to (\documentclass{article}\pagestyle{empty}\begin{document}$ \left({\matrix{ {e - \alpha } \cr {i - \alpha } \cr } } \right) $\end{document})((α + 1)n ‐ 2e) + (\documentclass{article}\pagestyle{empty}\begin{document}$ \matrix{ {e - \alpha - 1} \cr {i - \alpha - 1} \cr } $\end{document})(2e ‐αn). A necessary and sufficient condition for a multigraph G with given n and e to minimize mi(G) for an i with i ⩽ 2(α ‐ γ) ‐ 3 is presented. We also show that there exists a graph such that the lower bound is tight for all i in the range [α, 2(α ‐ γ) ‐ 3]. © 1994 by John Wiley & Sons, Inc.
Sequences of graphical invariants
Authors: Topp Jerzy 
Published: May 2007

AbstractFor a given graphical invariant π, a sequence (ao, a1,…, an) of positive integers is said to be π‐feasible if there exists a graph G with distinguished vertices ν1, ν2,…, νn such that π(G) = ao and π(G −ν1 −ν2 −…−νi) = ai for i = 1, 2,…,n. In this paper, we investigate π‐feasible sequences for the irredundance, domination, and independence numbers of a graph.
Edge‐tenacious networks
Authors: Piazza Barry L. , Robertst Fred S. , Stueckle Sam K. 
Published: May 2007

AbstractThe stability of a (communication or transportation) network composed of (processing) nodes and (communication or transportation) links is of prime importance to network designers. As the network begins losing links or nodes, eventually, there is a loss in its effectiveness. Thus, it is desirable that networks be constructed to be as stable as possible, not only with respect to the initial disruption, but also with respect to the possible reconfiguration of the network after disruption. Many graph theoretical parameters have been used in the past to describe the stability of networks, including the vertex‐connectivity and edge‐connectivity, toughness and edge‐toughness, integrity and edge‐integrity, and tenacity. In this paper, we study the edge‐tenacity of graphs. We will be primarily interested in edge‐tenacious graphs, which can be considered very stable and are somewhat analogous in edge‐tenacity to honest graphs in edge‐integrity. We prove several results about edge‐tenacious graphs as well as find numerous classes of edge‐tenacious graphs.
Multicommodity flows in simple multistage networks
Authors: Elmallah E. S. , Culberson J. C. 
Published: May 2007

AbstractIn this paper, we consider the integral multicommodity flow problem on directed graphs underlying two classes of multistage interconnection networks. In one direction, we consider three‐stage networks. Using existing results on (g, f)‐factors of bipartite graphs, we show sufficient and necessary conditions for the existence of a solution when the network has at most two secondary switches. In contrast, the problem is shown to be NP‐complete if the network has three or more secondaries. In a second direction, we introduce a recursive class of networks that includes multistage hypercubic networks (such as the omega network, the indirect binary n‐cube, and the generalized cube network) as a proper subset. Networks in the new class may have an arbitrary number of stages. Moreover, each stage may contain identical switches of any arbitrary size. The notion of extrastage networks is extended to the new class, and the problem is shown to have polynomial time solutions on r‐stage networks where r = 3 or where each link has a unit capacity and r ≥ 3. The latter result implies an efficient algorithm for deciding admissible permutations on conventional extrastage hypercubic networks. In contrast, we show that the multicommodity flow problem is NP‐complete on extrastage networks, even if r = 6, each link has an integral capacity ≤ 3, and all flow demands are equal.
Lower bounds for the length of test sequences using UIOs
Authors: Rodrigues Marion , Ural Hasan 
Published: May 2007

AbstractThe optimality of the length of a test sequence for a given finite‐state machine can be determined only with respect to the class of test sequences that employ the same number and type of state identification/verification (SIV) sequences and satisfy the same requirements for the starting and terminating states. Given a certain number and type of SIV sequences, we identify three different types of optimality for test sequences: Type11 requires test sequences to begin and end at the initial state; Type1y requires only that test sequences begin at the initial state; and Typexy imposes no requirements whatsoever on the starting and terminating states. Based on these definitions, we investigate the case where Unique Input Output (UIO) sequences are given as SIV sequences and derive lower bounds for the length of test sequences of Type11, Type1y, and Typexy.
Vertex domination‐critical graphs
Authors: Fulman Jason , Hanson Denis , Macgillivray Gary 
Published: May 2007

AbstractA graph G is vertex domination‐critical if for any vertex v of G the domination number of G ‐ v is less than the domination number of G. If such a graph G has domination number γ, it is called γ‐critical. Brigham et al. studied γ‐critical graphs and posed the following questions: (1) If G is a γ‐critical graph, is |V| ≥ (δ + 1)(γ ‐ 1) + 1?(2) If a γ‐critical graph G has (Δ + 1)(γ ‐ 1) + 1 vertices, is G regular? (3) Does i = γ for all γ‐critical graphs? (4) Let d be the diameter of the γ‐critical graph G. Does d ≤ 2(γ ‐ 1) always hold? We show that the first and third questions have a negative answer and the others have a positive answer.
Sales‐delivery man problems on treelike networks
Authors: Averbakh Igor , Berman Oded 
Published: May 2007

AbstractSuppose that customers who require some service are situated at nodes of a network. Service is provided by a server who performs a service tour through all the nodes. The server has two objectives: (1) minimize the total waiting time of the customers and (2) minimize the length of the tour. It is assumed that the latter objective is of primary importance. For routing and location‐routing variants of the problem on trees and cactus networks, polynomial algorithms are presented, most of them with complexity O(n log n) or O(n). Multiserver variants of the problem on a tree are proved to be NP‐complete. Some modifications of the problem are also investigated.
Simple heuristics for unit disk graphs
Authors: Marathe M. V. , Breu H. , Hunt H. B. , Ravi S. S. , Rosenkrantz D. J. 
Published: May 2007

AbstractUnit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP‐hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring, and minimum dominating set. We also present an on‐line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and intersection graphs of higher dimensional regular objects.
Thirty‐five‐point rectilinear steiner minimal trees in a day
Authors: Salowe Jeffrey S. , Warme David M. 
Published: May 2007

AbstractGiven a set of terminals in the plane, a rectilinear Steiner minimal tree is a shortest interconnection among these terminals using only horizontal and vertical edges. We present an algorithm that constructs a rectilinear Steiner minimal tree for any input terminal set. On a workstation, problems involving 20 input terminals can be solved in a few seconds, and problems involving 30 input terminals can be solved, on average, in 30 min. Previous algorithms could only solve 16‐ or 17‐point point problems within the 30 min time bound. Problems involving 35 points can be solved, on average, within a day. Our experiments were run on uniformly distributed data on an integer grid.
A capacity scaling algorithm for the constrained maximum flow problem
Authors: Ahuja Ravindra K. , Orlin James B. 
Published: May 2007

AbstractThe constrained maximum flow problem is to send the maximum possible flow from a source node s to a sink node t in a directed network subject to a budget constraint that the cost of flow is no more thanD. In this paper, we consider two versions of this problem: (i) when the cost of flow on each arc is a linear function of the amount of flow, and (ii) when the cost of flow is a convex function of the amount of flow. We suggest capacity scaling algorithms that solve both versions of the constrained maximum flow problem in O((m log M) S(n, m)) time, wherenis the number of nodes in the network;m, the number of arcs; M, an upper bound on the largest element in the data: and S(n, m), the time required to solve a shortest path problem with nonnegative arc lengths. Our algorithms are generalizations of the capacity scaling algorithms for the minimum cost flow and convex cost flow problems and illustrate the power of capacity scaling algorithms to solve variants of the minimum cost flow problem in polynomial time.
Threshold reliability of networks with small failure sets
Authors: Ball Michael O. , Hagstrom Jane N. , Provan J. Scott 
Published: May 2007

AbstractThis paper addresses two classes of reliability analysis models: a network flow model and a project scheduling model. In each model, the arcs randomly and independently take on two possible states–an “operating” state and a “failed” state–corresponding to two different capacity/task‐time values, and the network is required to maintain a specified “threshold” max‐flow/project‐completion‐time value. In general, this problem is NP‐hard. We address the special case in which the difference between the lower and higher arc lengths is constant for every arc in the network. For these special cases, we show that if the underlying system is 1‐critical, i.e., minimally able to withstand a single component failure, then the probability that the system can maintain the required threshold for the flow and planar project scheduling model is computable in polynomial time. Both solutions are obtained by reducing the problems to the problem of determining the probability that the failed arcs in a directed acyclic graph lie on a single path or, equivalently, that the set of failed elements in a given partial order comprises a chain in that order. We also show how the basic approach can be used to generate bounds for systems that are “almost critical”.
On reliability evaluation of a capacitated‐flow network in terms of minimal pathsets
Authors: Lin Jsen‐Shung , Jane Chin‐Chia , Yuan John 
Published: May 2007

AbstractMany real‐world systems such as electric power transmission and distribution systems, transportation systems, and manufacturing systems can be regarded as flow networks whose arcs have independent, finite, and multivalued random capacities. Such a flow network is indeed a multistate system with multistate components and so its reliability for the system demand d, i.e., the probability that the maximal flow is no less than d, can be computed in terms of minimal path vectors to level d (named d‐MPs here). The main objective of this paper was to present a simple algorithm to generate all d‐MPs of such a system for each system capacity level d in terms of minimal pathsets. Analysis of our algorithm and comparison to Xue's algorithm shows that our method has the following advantages: (1) the family of d‐MP candidates that it generates is smaller in size and so d‐MPs can be generated more efficiently, (2) it is expressed more intuitively and so easier to understand, and (3) whenever applied in a series‐parallel case, both algorithms are essentially the same, but in a non series‐parallel case, Xue's algorithm needs the extra work to transform the system into a series‐parallel in advance. Two examples are illustrated to show how all d‐MPs are generated by our algorithm and then the reliability of one example is computed.
A survey of efficient reliability computation using disjoint products approach
Authors: Rai Suresh , Veeraraghavan Malathi , Trivedi Kishor S. 
Published: May 2007

AbstractSeveral algorithms have been developed to solve the reliability problem for nonseries‐parallel networks using thesum of disjoint products (SDP)approach. This paper provides a general framework for most of these techniques. It reviews methods that help improve computer time and memory requirements in reliability computation. These parameters are generally used to compare SDP algorithms. We also overview three multiple variable inversion algorithms that result in sum of disjoint products expressions with fewer terms than that of algorithms that use only a single‐variable inversion. One common network is solved for two‐terminal network reliability using each of these algorithms. Finally, we have provided a comparison among these techniques.
On truncated‐newton methods for solving the spatial price equilibrium problem
Authors: Florian M. , Thomas S. J. , Zahar R. V. M. 
Published: May 2007

AbstractA truncated‐Newton method is applied to the spatial price equilibrium problem and the method is compared with other specialized techniques that exploit the inherent network structure of the problem. Variants of the linear conjugate gradient algorithm for approximately solving the Newton equations are discussed. Numerical results for the truncated‐Newton method are compared with those of a block‐SOR method. Tests indicate that the two approaches are comparable when transportation costs are linear. A truncated‐Newton algorithm is far superior if the transportation costs are nonlinear.
Recognizing small subgraphs
Authors: Sundaram Gopalakrishnan , Skiena Steven S. 
Published: May 2007

AbstractAlthough the general problem of subgraph isomorphism is NP‐complete, polynomial‐time algorithms exist for recognizing any fixed subgraph. However, certain subgraphs appear easier to recognize than others. In this paper, we present general algorithms for fixed‐subgraph isomorphism which improve or unify previous results. In particular, we present an O(nfm) algorithm for recognizing a fixed subgraph H with flower number f within a graph G with n vertices and m edges. Special cases of this algorithm match the best algorithms known for recognizing small paths, cycles, and cliques. Further, we improve previous results for recognizing C5 and small even cycles C2k, k ≥ 3.
Graphs with not too many spanning trees
Authors: Ding Guoli 
Published: May 2007

AbstractLet 𝒢 be a class of graphs that is closed under taking topological minors. We derive in this paper some necessary and sufficient conditions for the existence of a polynomial p(n) such that t(G) ≤ p(|E(G)|) for all graphs G in 𝒢, where t(G) is the number of spanning trees of G.
The prize collecting traveling salesman problem: II. Polyhedral results
Authors: Balas Egon 
Published: May 2007

AbstractThe task of developing daily schedules for a steel rolling mill has been formulated as a Prize Collecting Traveling Salesman (PCTS) Problem, in which a salesman who gets a prize for every city he visits seeks a minimum‐cost tour including enough cities to collect a required amount of prize money. This paper addresses the facial structure of the PCTS polytope, the convex hull of solutions to the PCTS problem. In an earlier paper, we generalized to the PCTS polytope the subtour elimination inequalities for the Asymmetric Traveling Salesman (ATS) polytope. Here, we give a general method for deriving a facet defining inequality for the PCTS polytope from any facet defining inequality for the ATS polytope. We apply the procedure to several well‐known families of facet inducing inequalities for the ATS polytope: comb, odd CAT, SD, clique tree, and lifted cycle inequalities. We also extend the cloning and clique lifting procedure for the ATS polytope to the PCTS polytope.
Repeated uncoordinated information dissemination by flooding
Authors: Topkis Donald M. 
Published: May 2007

AbstractA dynamic database in a communications network consists of a set of messages, where a sequence of different versions of each message is generated over time in a repeated and uncoordinated process and where the appearances of the various message versions are distributed among the nodes. The message versions are to be disseminated in the network so that each message version eventually resides at each node. Flooding is a distributed procedure for disseminating message versions. The use of flooding to disseminate repeated and uncoordinated message versions is an integral part of a generic adaptive routing mechanism similar to that used in ARPANET and proposed for the INTERNET and is an element of a method proposed for improving survivability in intra‐LATA networks. A model is formulated to analyze the performance of the dissemination by flooding of repeated and uncoordinated message versions. The worst‐case time complexity is established, showing that flooding is an optimal procedure in terms of this measure. Special properties of flooding in a tree are also established. A key parameter is a separator, which is a lower bound on the time interval between the initial generation of a particular version of any message and the initial generation of the next version of that message.
An improved heuristic for the period vehicle routing problem
Authors: Chao I‐Ming , Golden Bruce L. , Wasil Edward 
Published: May 2007

AbstractIn the period vehicle routing problem, each customer requires a certain number of deliveries per week. Given these frequency requirements, customers must be allocated to days. A vehicle routing problem is solved over each day. We have improved upon best‐known solutions to problems from the literature using a new heuristic procedure. The heuristic also works well on 19 newly generated test problems.