bluuebunny/crossref_metadata_2025_split huggingface dataset:
The probabilistic minimum spanning tree problem
Authors: Bertsimas Dimitris J. 
Published: May 2007

AbstractIn this paper we consider a natural probabilistic variation of the classical minimum spanning tree problem (MST), which we call the probabilistic minimum spanning tree problem (PMST). In particular, we consider the case where not all the points are deterministically present, but are present with certain probability. We discuss the applications of the PMST and find a closed‐form expression for the expected length of a given spanning tree. Based on these expressions, we prove that the problem is NP‐complete. We further examine some interesting combinatorial properties of the problem, establish the relation of the PMST with the MST and the network design problem, and examine some cases where the problem is solvable in polynomial time. We finally characterize the asymptotic behavior of reoptimization strategies, in which we find the MST or the Steiner tree, respectively, among the points that are present on a particular instance, and the PMST, in the case in which points are randomly distributed in the Euclidean plane and in the case in which the costs of the ares are randomly distributed. In both cases the PMST is within constant factors from both strategies.
Combining monte carlo estimates and bounds for network reliability
Authors: Nel Louis D. , Colbourn Charles J. 
Published: May 2007

AbstractA simplified model of a communications network is a probabilistic graph in which each edge operates with the same probability. The all‐terminal reliability, or probability that all nodes are connected, can be expressed as a polynomial in the edge operation probability. The coefficients of this polynomial are obtained from an interval partitioning of the cographic matroid, and only the first few coefficients can be computed efficiently. One of the best sets of efficiently computable reliability bounds is the Ball‐Provan bounds. These bounds are obtained using the efficiently computable coefficients and can be improved substantially if additional coefficients are known. In this paper, we develop a Monte Carlo method for estimating additional coefficients by randomly sampling over spanning trees of the network. Confidence intervals for all‐terminal reliability are obtained by using these estimates as additional constraints in the Ball‐Provan bounds. This approach has some advantages over conventional Monte Carlo point estimate methods. In particular, the computational complexity does not depend on the reliability of the network.
A characterization of partial 3‐trees
Authors: Satyanarayana A. , Tung L. 
Published: May 2007

AbstractA k‐tree is defined recursively as follows: The complete graph Kk on k points is a k‐tree. Given a k‐tree G on n ≤ k points, a k‐tree on n + 1 points is obtained by adding a new point u and edges connecting u to every point of a Kk in G. A graph is a partial k‐tree if it is a subgraph of some k‐tree. In this paper, we establish some interesting properties of partial 3‐trees and show that a graph is a partial 3‐tree if and only if it has no subgraph contractible to K5, K2.2.2 C8(1, 4), or K2 ≤ C5. A graph G is said to be contractible to a graph H if H can be obtained from G by a sequence of edge contractions. hitherto, such a characterization of partial k‐trees was known only for the values of k ≤ 2.
Fair dissections of spiders, worms, and caterpillars
Authors: De Simone Caterina , Lucertini Mario , Pallottino Stefano , Simeone Bruno 
Published: May 2007

AbstractIn the present paper we deal with equipartition problems for special classes of trees, i. e., spiders, stars, worms, and caterpillars. We prove that the equipartition problem is NP‐complete for spiders (and, hence, for general trees); on the other hand, we give efficient polynomial‐time algorithms for stars, worms, and caterpillars.
An application of lagrangean decomposition to the resource‐constrained minimum weighted arborescence problem
Authors: Guignard Monique , Rosenwein Moshe B. 
Published: May 2007

AbstractThe resource‐constrained minimum weighted arborescence problem, a 0‐1 integer programming model with application in hierarchical distribution network design, is introduced. Since the model is NP‐hard, an enumeration method is required to solve it to optimality. Lagrangean decomposition, a special form of Lagrangean relaxation, is applied to the model. Both analytically and empirically, Lagrangean decomposition is shown to improve on bounds obtained by a conventional Lagrangean relaxation. An enumeration algorithm, that embeds a specialized Lagrangean dual ascent scheme to solve a Lagrangean decomposition dual, is designed, and problems with up to 1000 0‐1 variables are solved.
Disjoint (s, t)‐cuts in a network
Authors: Wagner Donald K. 
Published: May 2007

AbstractConsider a graph having distinguished vertices s and t, and a nonnegative, real‐valued cost associated with each edge. This paper considers variations on the problem of finding k pairwise‐disjoint (s, t)‐cuts of minimum total cost. For k = 1, this problem is a version of the well‐known minimum‐cut problem from network‐flow theory and, thus, is solvable in polynomial time. The main result of this paper is that for arbitrary k, the problem can be formulated as a specially structured transshipment problem and, thus, is solvable in polynomial time.
A heuristic algorithm for a network problem with variable upper bounds
Authors: Shetty Bala 
Published: May 2007

AbstractWe present a heuristic algorithm for the solution of a network problem with variable upper bounds. This algorithm is motivated by the desire to exploit the special structure of the variable upper bound (VUB) constraints and to maintain as much of the characteristics of pure network problems as possible. Our solution technique for the VUB problem consists of solving two sequences of pure network problems. One sequence yields tighter lower bounds on the optimal objective value by considering the Lagrangean relaxation in which the VUB constraints are dualized. The second sequence yields upper bounds on the optimal value for the problem. This sequence is obtained by considering a reformulation of the VUB problem based on parametric changes in the variable upper bound. The algorithm has been tested on problems with as many as 1500 nodes, 6600 arcs, and 3000 VUB constraints. Computational experience with the solution of randomly generated fixed‐charge network problems, capacitated warehouse location problems, and production smoothing problems is also reported.
Relaxation methods for the strictly convex multicommodity flow problem with capacity constraints on individual commodities
Authors: Nagamochi Hiroshi , Fukushima Masao , Lbaraki Toshihide 
Published: May 2007

AbstractWe study the multicommodity flow problem that minimizes a strictly convex cost objective function subject to the capacity constraints on individual commodities as well as the total flows in each arc. By making use of its dual, we formulate the problem as a nonlinear unconstrained optimization problem and propose relaxation methods. Computational results show that the proposed methods can practically solve problem instances, for example, with up to 100 nodes, 1000 arcs, and seven commodities.
Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle
Authors: Agarwal Pankaj Kumar , Shing Man‐Tak 
Published: May 2007

AbstractThe general rectilinear Steiner tree problem has been proved to be NP‐complete. In this paper, we consider a special case in which the points lie on the boundary of a rectilinear rectangle and give anO(n)algorithm to construct a minimum rectilinear Steiner tree for such points.
Identifying independence in bayesian networks
Authors: Geiger Dan , Verma Thomas , Pearl Judea 
Published: May 2007

AbstractAn important feature of Bayesian networks is that they facilitate explicit encoding of information about independencies in the domain, information that is indispensable for efficient inferencing. This article characterizes all independence assertions that logically follow from the topology of a network and develops a linear time algorithm that identifies these assertions. The algorithm's correctness is based on the soundness of a graphical criterion, calledd‐separation, and its optimality stems from the completeness ofd‐separation. An enhanced version ofd‐separation, calledD‐separation, is defined, extending the algorithm to networks that encode functional dependencies. Finally, the algorithm is shown to work for a broad class of nonprobabilistic independencies.
An ordered examination of influence diagrams
Authors: Shachter Ross D. 
Published: May 2007

AbstractInfluence diagrams are a directed network representation for decision making under uncertainty. The nodes in the diagram represent uncertain and decision variables, and the arcs indicate probabilistic dependence and observability. This paper examines the graphical orderings underlying the influence diagram and the primitive interchange operations that can reorder the network. These operations are sufficient to determine the maximal independent set and minimal relevant sets for any given inference problem, and a linear time algorithm is developed to obtain those sets. This framework is also used to examine and explain properties of the time structure of general influence diagrams with decisions.
Sequential updating of conditional probabilities on directed graphical structures
Authors: Spiegelhalter David J. , Lauritzen Steffen L. 
Published: May 2007

AbstractA directed acyclic graph or influence diagram is frequently used as a representation for qualitative knowledge in some domains in which expert system techniques have been applied, and conditional probability tables on appropriate sets of variables form the quantitative part of the accumulated experience. It is shown how one can introduce imprecision into such probabilities as a data base of cases accumulates. By exploiting the graphical structure, the updating can be performed locally, either approximately or exactly, and the setup makes it possible to take advantage of a range of well‐established statistical techniques. As examples we discuss discrete models, models based on Dirichlet distributions and models of the logistic regression type.
Probabilistic similarity networks
Authors: Heckerman David 
Published: May 2007

AbstractWe address the pragmatics of constructing normative expert systems and examine the influence diagram as a potential framework for representing knowledge in such systems. We introduce an extension of the influence‐diagram representation called asimilarity network.A similarity network is a tool for constructing large and complex influence diagrams. The representation allows a user to construct independent influence diagrams for subsets of a given domain. A valid influence diagram for the entire domain can then be constructed from the individual diagrams. Similarity networks represent forms of conditional independence that are not represented conveniently in an ordinary influence diagram. We discuss in detail one such conditional independence, calledsubset independence, and examine how similarity networks exploit this form of independence to facilitate the construction of an influence diagram. Also, we investigate the assessment of probability distributions for influence diagrams. We see that similarity networks exploit subset independence to simplify such probability assessments. We introduce a representation that is closely related to similarity networks, called apartition.This representation further exploits subset independence to simplify probability assessment. Finally, we examine a real‐world normative expert system for the diagnosis of lymph‐node pathology, called Pathfinder. The similarity‐network and partition representations played a crucial role in the construction of this expert system.
An algebra of bayesian belief universes for knowledge‐based systems
Authors: Jensen Finn Verner , Olesen Kristian G. , Andersen Stig Kjaer 
Published: May 2007

AbstractCausal probabilistic networks (CPNs) have proved to be a useful knowledge representation tool for modeling domains where causal relations‐in a broad sense‐are a natural way of relating domain concepts and where uncertainty is inherited in these relations. The domain is modeled in a CPN by use of a directed graph where the nodes represent concepts in the domain and the arcs represent causal relations. Furthermore, the quantitative relation between a node and its immediate causes is expressed as conditional probabilities. During the last few years, several schemes based on probability theory for incorporating and propagating new information throughout a CPN has emerged. As long as the domain can be modeled by use of a singly connected CPN (i. e., no more than one path between any pair of nodes), the schemes operate directly in the CPN and perform conceptually simple operations in this structure. When it comes to more complicated structures such as multiply connected CPNs (i. e., more than one path is allowed between pairs of nodes), the schemes operate in derived structures where the embedded domain knowledge no longer is as explicit and transparent as in the CPN. Furthermore, the simplicity in the operations is lost also. This report outlines a scheme‐the algebra ofBayesian belief universes‐for absorbing and propagating evidence in multiply connected CPNs. The scheme provides a secondary structure,a junction tree, and a simple set of algebraic operations between objects in this structure,Collect EvidenceandDistribute Evidence.These are the basic tools for making inference in a CPN domain model and yield a calculus as simple as in the case of singly connected CPNs.
A randomized approximation algorithm for probabilistic inference on bayesian belief networks
Authors: Chavez R. Martin , Cooper Gregory F. 
Published: May 2007

AbstractResearchers in decision analysis and artificial intelligence (AI) have used Bayesian belief networks to build probabilistic expert systems. Using standard methods drawn from the theory of computational complexity, workers in the field have shown that the problem of probabilistic inference in belief networks is difficult and almost certainly intractable. We have developed a randomized approximation scheme, BN‐RAS, for doing probabilistic inference in belief networks. The algorithm can, in many circumstances, perform efficient approximate inference in large and richly interconnected models. Unlike previously described stochastic algorithms for probabilistic inference, the randomized approximation scheme (ras) computes a priori bounds on running time by analyzing the structure and contents of the belief network. In this article, we describe BN‐RAS precisely and analyze its performance mathematically.
Graphical inference in qualitative probabilistic networks
Authors: Wellman Michael P. 
Published: May 2007

AbstractQualitative probabilistic networks (QPNs) are abstractions of influence diagrams that encode constraints on the probabilistic relation among variables rather than precise numeric distributions. Qualitative relations express monotonicity constraints on direct probabilistic relations between variables or on interactions among the direct relations. Like their numeric counterpart, QPNs facilitate graphical inference: methods for deriving qualitative relations of interest via graphical transformations of the network model. However, query processing in QPNs exhibits, computational properties quite different from basic influence diagrams. In particular, the potential for information loss due to the incomplete specification of probabilities poses the new challenge of minimizing ambiguity. Analysis of the properties of QPN transformations reveals several characteristics of admissible graphical inference procedures.
On the construction of optimally reliable graphs
Authors: Smith Derek H. , Doty Lynne L. 
Published: May 2007

AbstractWe consider the reliability of regular graphs of degree k in which the vertices of the graph fail independently with probability p. The probability of disconnection is minimized for small values of p if the graph has connectivity k and has the smallest number of vertex cut sets with k vertices. In this paper, we show how to construct such graphs.
Hierarchical solution of network flow problems
Authors: Lyer Anant H. V. , Jarvis John J. , Ratliff H. Donald 
Published: May 2007

AbstractGiven a network flow problem and a partition of its nodes into disjoint sets, we provide an aggregation‐disaggregation procedure that reformulates the problem as the union of network flow subproblems. Each subproblem either involves nodes in a set and their induced arcs or involves nodes and arcs between a pair of node sets. We present a hierarchical solution procedure, based on ficitious play of a two‐person game, that solves each of the subproblems separately at each iteration, retains network structure of each of the subproblems across iterations, generates upper and lower bounds to the objective function value at each iteration, and converges asymptotically to the global optimal solution. We apply the algorithms to a logistics planning model involving uncapacitated transportation problems and provide computational results for problem reformulations based on two different partitions. When the procedure is initialized with a good initial solution, we observe excellent convergence rates for the optimality gap across iterations. We also discuss relationships between our approach and Benders' decomposition and provide an example comparing the objective function values of solutions generated by the two approaches.
Time‐dependent traveling salesman problem–the deliveryman case
Authors: Lucena Abilio 
Published: May 2007

AbstractWe consider a scheme to derive lower bounds for the time‐dependent traveling salesman problem. It involves splitting lower bounds into a number of components and optimizing each of these components. The lower bounds thus derived are shown to be at least as sharp as the ones previously suggested for the problem. We describe a branch‐and‐bound algorithm based on our lower bounding scheme and computationally test it for an instance of the problem known as the traveling deliveryman problem.
Optimal locations and districts of two traveling salesmen on a tree
Authors: Simchi‐Levi David , Berman Oded 
Published: May 2007

AbstractThis paper focuses on the problem of locating on a tree two service units that must service each working day all the customers that require service. The paper includes an O(n2) algorithm to find the optimal locations that minimize the expected distance traveled by the two service units. This algorithm also gives the optimal service territories of the two service units. The algorithm is based on an available O(n) algorithm to find the optimal location of a single service unit on a tree and on a new method to calculate the objective function value of a given location for the single server.
Predicting deadlock in store‐and‐forward networks
Authors: Arbib Claudio , Italiano Gluseppe F. , Panconesl Alessandro 
Published: May 2007

AbstractWe consider the problem of predicting whether a deadlock will necessarily occur in a store‐and‐forward network. We define two versions of this problem, depending on whether or not the routes to be followed by packets are fixed. For networks with only one buffer per vertex, both versions of this problem are shown to be NP‐complete even for simple classes of graphs (among others bipartite graphs, two terminal series‐parallel [TTSP] graphs and therefore planar graphs). On the other hand, the same problems are shown to be polynomially solvable for treelike networks. In this case, two efficient algorithms for checking whether a treelike network with n vertices and p packets is bound to deadlock are proposed. The former has an O(pn) time and space complexity, whereas the latter runs in O(n log n)1 time and requires O(n) space. In the case of multibuffered networks, both versions of the problem are shown to be NP‐complete even on treelike networks.
Efficient algorithms for computing the reliability of permutation and interval graphs
Authors: Aboeifotoh Hosam M. , Colbourn Charles J. 
Published: May 2007

AbstractA stochastic network in which nodes fail randomly with known probabilities is modeled by a probabilistic graph with unreliable nodes and perfect edges. The K‐terminal reliability of such a network is the probability that there exists a Steiner tree connecting a subset of the nodes K (target nodes). Although the K‐terminal reliability problem has been widely studied for networks with unreliable links, very little is known about the problem for networks with unreliable nodes. We show that computing this measure is computationally difficult, in particular #P‐complete. We then present efficient algorithms for the K‐terminal reliability problem on two classes of perfect graphs; interval graphs and permutation graphs. Computing the reliability on these two classes of graphs is of particular interest since the problem remains #P‐complete for larger classes in the hierarchy of perfect graphs, namely, comparability and chordal graphs. The model presented in this paper is appropriate for radio broadcast networks and for fault‐tolerant multiprocessor networks.
Minimal diameter double‐loop networks: Dense optimal families
Authors: Bermond J.‐C. , Tzvieli Dvora 
Published: May 2007

AbstractThis article deals with the problem of minimizing the transmission delay in Illiac‐type interconnection networks for parallel or distributed architectures or in local area networks. A double‐loop network (also known as circulant) G(n,h), consists of a loop of n vertices where each vertex i is also joined by chords to the vertices i ± h mod n. An integer n, a hop h, and a network G(n,h) are called optimal if the diameter of G(n,h) is equal to the lower bound k when n ∈ R[k] = {2k2 − 2k + 2, …,2k2 + 2k + 1}. We determine new dense families of values of n that are optimal and such that the computation of the optimal hop is easy. These families cover almost all the elements of R[k] if k or k + 1 is prime and cover 92% of all values of n up to 106.
Centroids to centers in trees
Authors: Reid K. B. 
Published: May 2007

AbstractIf k is a nonnegative integer and x is a vertex of a tree T, the k‐ball branch weight of x, denoted b(x;k), is the number of vertices in a largest subtree of T, all of whose vertices are a distance at least k + 1 from x. The k‐ball branch weight centroid of T, denoted W(T;k), consists of all vertices x of T for which b(x;k) is a minimum. The usual branch weight centroid of T (which is also the median) is W(T;0), and the center of T is W(T;r), where r is the radius of T. In this paper, the structure of the subgraph spanned by W(T;k) is examined. Similarities and differences with Slater's k‐centrum [6] and k‐nucleus [7] are discussed.
Efficient algorithms for inferring evolutionary trees
Authors: Gusfield Dan 
Published: May 2007

AbstractIn this paper, we examine two related problems of inferring the evolutionary history of n objects, either from present characters of the objects or from several partial estimates of their evolutionary history. The first problem is called the Phylogeny problem, and second is the Tree Compatibility problem. Both of these problems are central in algorithmic approaches to the study of evolution and in other problems of historical reconstruction. In this paper, we show that both of these problems can be solved by graph theoretic methods in linear time, which is time optimal, and which is a significant improvement over existing methods.