Combinatorial methods for constructing bipartite uniform minimal quasicomplete graphs (symmetrical block designs)

Consideration was given to a specific family of bipartite graphs consisting of two disjoint subsets X and Y of vertices and characterized by that each vertex in X (Y) is connected to each of the remaining vertices in X (Y) by a unique path of length two passing through some vertex in Y (X). The prefix “quasi” reflects the fact that complete connection of the vertices is realized by paths of length two rather than by edges. The problem of constructing uniform minimal graphs with identical cardinalities of the subsets X and Y which is of practical interest for complex communication networks was discussed. It belongs to the class of combinatorial problems of construction of the so-called symmetrical block designs.     

Knowledge representation using fuzzy deduction graphs

A new knowledge representation model, known as fuzzy deduction graph (FDG), is introduced in this paper. An FDG can represent a knowledge base containing the fuzzy propositions and fuzzy rules. In an FDG, a systematic method of finding the fuzzy reasoning path (FRP) is given which is based on Dijkstra's shortest path framework. The FRP gives a relationship between the antecedent (source) proposition and consequent (goal) proposition, such that the consequent proposition is reached with the greatest fuzzy value. The process of finding the FRP is illustrated with examples.     

Algorithms for searching massive graphs

Given a large graph, stored on disk, there is often a need to perform a search over this graph. Such a need could arise, for example, in the search component of a data-intensive expert system or to solve path problems in deductive database systems. In this paper, we present a novel data structuring technique and show how a branch-and-bound search algorithm can use this data structuring to prune the search space. Simulation results confirm that, using these techniques, a search can be expedited significantly without incurring a large storage penalty. As a side benefit, it is possible to organize the search to obtain successive approximations to the desired solution with considerable reduction in the total search     

On minimal graphs

Graphs, regarded as grammar forms as well as coloring specifications, induce graph-families, so-called color-families. It can be shown that for each color-family a unique (vertex) minimal graph exists. In this paper an operation on such minimal graphs is presented. As a main result it is shown that in a minimal graph G with m vertices, none of them adjacent to all other vertices, cliques have less than $\text{1}\text{2}$m vertices and this bound cannot be improved.     

Integrating integer programming and probabilistic deduction graphs for probabilistic reasoning

Optimal solutions of several variants of the probabilistic reasoning problem were found by a new technique that integrates integer programming and probabilistic deduction graphs (PDG). PDGs are extended from deduction graphs of the and-type via normal deduction graphs. The foregoing variants to be solved can involve multiple hypotheses and multiple evidences where the former is given and the latter is unknown and being found or vice versa. The relationship among these hypotheses and evidences with possible intermediaries is represented by a causal graph. The proposed method can handle a large causal graph of any type and find an optimal solution by invoking a linear integer programming package. In addition, formulating the reasoning problem to fit integer programming takes a polynomial time. H.-L. Li was visiting the Department of Computer Sciences, University of North Texas in 1988–1989. He is with the Institute of Information Management, National Chiao Tung University, Hsinchu, Taiwan, R.O.C.     

Algorithms for updating minimal spanning trees

The problem of finding the minimal spanning tree on an undirected weighted graph has been investigated by many people and O(n²) algorithms are well known. P. M. Spira and A. Pan (Siam J. Computing4 (1975), 375–380) present an O(n) algorithm for updating the minimal spanning tree if a new vertex is inserted into the graph. In this paper, we present another O(n) algorithm simpler than that presented by Spira and Pan for the insertion of a vertex. Spira and Pan further show that the deletion of a vertex requires O(n²) steps. If all the vertices are considered, O(n³) steps may be used. The algorithm which we present here takes only O(n²) steps and labels the vertices of the graph in such a way that any vertex may be deleted from the graph and the minimal spanning tree can be updated in constant time. Similar results are obtained for the insertion and the deletion of an edge.     

Algorithms for routing in planar graphs

Summary A routing problem is given by a planar graph G= (V, E) with a given embedding into the plane and a set Ne of nets. A net is a pair of points on the boundary of the infinite face. The goal is to find a set of pairwise edge-disjoint paths connecting the terminals of the various nets. We assume that the degree of every vertex not on the boundary of the infinite face is even and call such routing problems half-even. We show that one can decide in time O(bn) whether a half-even problem is solvable and that a solution can be constructed in time O(n ²). Here n=¦V¦ and b is the number of vertices on the boundary of the infinite face. If the routing problem is even, i.e. every cut has even free capacity, and G is a subgraph of the planar grid then a solution can be found in time O(n ^3/2).This research was supported by the Deutsche Forschungsgemeinschaft, SFB 124, VLSI-Entwurfsmethoden und Parallelität. Part of it was done while the second author was visiting SIEMENS A.G., ZTI VENUS     

Algorithms for constructing optimal controllers for gaslift operation

We consider the optimal stabilization problem for delivered gas and gaslift operation debit for oil wells. Under certain natural assumptions, the general problem reduces to a linear-quadratic control problem that lets us find program controls and trajectories on which we further construct the optimal controller with respect to all phase coordinates and a (debit) part of them in both continuous and discrete case. For a special case, numerical results are illustrated with graphs that let us use this method in oilfield practice.     

A simple BASIC program for constructing three-dimensional graphs

This report describes a simple program for plotting three-dimensional curves and thus allowing a visual representation of the simultaneous interaction of three variables. Graphs can be displayed on the screen or printed using a graphics printer. The original data can be stored, printed, recalled and edited, as can the graph parameters. Completed graphs can also be stored for later review or printing. The program as outlined can accommodate up to 10 curves of up to 50 points each, but these limits can be easily increased. The program is written in BASIC, thus allowing it to be readily modified. As listed, the complete source code has 357 lines and occupies about 12 kilobytes when saved in compressed binary format.     

Algorithms for multicommodity flows in planar graphs

This paper gives efficient algorithms for the muiticommodity flow problem for two classes C₁₂ and C₀₁ of planar undirected graphs. Every graph in C₁₂ has two face boundaries B₁ and B₂ such that each of the source-sink pairs lies on B₁ or B₂. On the other hand, every graph inC ₀₁ has a face boundaryB ₁ such that some of the source-sink pairs lie onB ₁ and all the other pairs share a common sink lying onB ₁. The algorithms run inO(kn +nT(n)) time if a graph hasn vertices andk source-sink pairs andT(n) is the time required for finding the single-source shortest paths in a planar graph ofn vertices.     

Algorithms for multicommodity flows in planar graphs

This paper gives efficient algorithms for the muiticommodity flow problem for two classes C₁₂ and C₀₁ of planar undirected graphs. Every graph in C₁₂ has two face boundaries B₁ and B₂ such that each of the source-sink pairs lies on B₁ or B₂. On the other hand, every graph inC ₀₁ has a face boundaryB ₁ such that some of the source-sink pairs lie onB ₁ and all the other pairs share a common sink lying onB ₁. The algorithms run inO(kn +nT(n)) time if a graph hasn vertices andk source-sink pairs andT(n) is the time required for finding the single-source shortest paths in a planar graph ofn vertices.     

A method for constructing minimal linear-analytic realizations for polynomial systems

For a polynomial nonlinear system described in terms of regular transfer functions, the shift-realization approach to constructing minimal bilinear realizations is modified to yield a method for constructing minimal linear-analytic realizations.     

A practical algorithm for making filled graphs minimal

For an arbitrary filled graph G⁺ of a given original graph G, we consider the problem of removing fill edges from G⁺ in order to obtain a graph M that is both a minimal filled graph of G and a subgraph of G⁺. For G⁺ with f fill edges and e original edges, we give a simple O(f(e+f)) algorithm which solves the problem and computes a corresponding minimal elimination ordering of G. We report on experiments with an implementation of our algorithm, where we test graphs G corresponding to some real sparse matrix applications and apply well-known and widely used ordering heuristics to find G⁺. Our findings show the amount of fill that is commonly removed by a minimalization for each of these heuristics, and also indicate that the runtime of our algorithm on these practical graphs is better than the presented worst-case bound.     

A self-stabilizing algorithm for constructing weakly connected minimal dominating sets

This paper presents a new distributed self-stabilizing algorithm for the weakly connected minimal dominating set problem. It assumes a self-stabilizing algorithm to compute a breadth-first tree. Using an unfair distributed scheduler the algorithm stabilizes in at most O(nmA) moves, where A is the number of moves to construct a breadth-first tree. All previously known algorithms required an exponential number of moves.     

On the problems of constructing minimal realizations for two-dimensional filters

The input-output behavior of a two-dimensional linear filter is defined by a formal power series in two variables. If the power series is rational the dynamics of the filter is described by updating equations on finite dimensional local state spaces. The class of realizations considered in this paper is constituted by doubly indexed dynamical systems of reduced structure. The construction of the class of minimal realizations is based on matrix representation techniques of noncommutative power series.     

A note on constructing minimal linear-analytic realizations for polynomial systems

A procedure is given for constructing a simplified version of Crouch's form for minimal linear-analytic realizations of degree-3 polynomial systems.