A graph theoretic approach to matrix inversion by partitioning

LetM be a square matrix whose entries are in some field. Our object is to find a permutation matrixP such thatPM P ^–1 is completely reduced, i.e., is partitioned in block triangular form, so that all submatrices below its diagonal are 0 and all diagonal submatrices are square and irreducible. LetA be the binary (0, 1) matrix obtained fromM by preserving the 0's ofM and replacing the nonzero entries ofM by 1's. ThenA may be regarded as the adjacency matrix of a directed graphD. CallD strongly connected orstrong if any two points ofD are mutually reachable by directed paths. Astrong component ofD is a maximal strong subgraph. Thecondensation D ^* ofD is that digraph whose points are the strong components ofD and whose lines are induced by those ofD. By known methods, we constructD ^* from the digraph,D whose adjacency matrixA was obtained from the original matrixM. LetA ^* be the adjacency matrix ofD ^*. It is easy to show that there exists a permutation matrixQ such thatQA ^* Q ^–1 is an upper triangular matrix. The determination of an appropriate permutation matrixP from this matrixQ is straightforward.This was an informal talk at the International Symposium on Matrix Computation sponsored by SIAM and held in Gatlinburg, Tennessee, April 24–28, 1961 and was an invited address at the SIAM meeting in Stillwater, Oklahoma on August 31, 1961     

A chance-constrained approach to stochastic line balancing problem

In this paper, chance-constrained 0–1 integer programming models for the stochastic traditional and U-type line balancing (ULB) problem are developed. These models are solved for several test problems that are well known in the literature and the computational results are given. In addition, a goal programming approach is presented in order to increase the system reliability, which is arising from the stochastic case.     

An intersection graph of straight lines

G. Ehrlich, S. Even, and R.E. Tarjan conjectured that the graph obtained from a complete 3 partite graph K_4,4,4 by deleting the edges of four disjoint triangles is not the intersection graph of straight line segments in the plane. We show that it is.     

Representing a planar graph by vertical lines joining different levels

Answering a problem of H. de Fraysseix and P. Rosenstiehl we prove that every planar graph can be represented by horizontal segments corresponding to vertices and vertical segments corresponding to edges in such a way that no crossing appears. For 2-connected planar graphs, the boundary of the representation can be prescribed.     

A goal programming approach to simple U-line balancing problem

In this paper, a goal programming model for the simple U-line balancing (ULB) problem is developed. The model is based on the integer programming formulation developed by Urban [Urban, Note: Optimal balancing of U-shaped assembly lines, Management Science 44(5) (1998) 738–741] for the ULB problem and the goal model of Deckro and Rangachari [Deckro, Rangachari, A goal approach to assembly line balancing, Computers and Operations Research 17 (1990) 509–521] developed for the traditional single model assembly line balancing (ALB) problem. The proposed model which is the first multi-criteria decision making approach to the U-line version provides increased flexibility to the decision maker since several conflicting goals can be simultaneously considered.     

A case study of an adaptive load balancing algorithm

In this paper we present an effective load balancing algorithm for a multi-processor architecture designed for the real time switching of telephone calls. By modifying an algorithm developed for an abstract queueing model, which is of independent interest by itself, we propose a hybrid load balancing algorithm and study its performance in a simulation test-bed. This case study demonstrates how simple abstractions and theoretically intractable but intuitively appealing ideas can be combined to effectively solve a real problem.     

Projective graph theory and configurations of lines

The spaces of disjoint configurations of k-dimensional subspaces in ℝP ^2k+1 (for example, lines in ℝP ³) are studied. These spaces are modeled by various simplicial schemes, and the homology groups of the latter are computed in certain cases. We use the fact that every configuration can be assigned a so-called projective graph, which is a class of graphs with respect to a certain equivalence relation. Bibliography: 5 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 231, 1995, pp. 309–322. Translated by N. Yu. Netsvetaev.     

The graph coloring problem: A neuronal network approach

Solution of an optimization problem with linear constraints through the continuous Hopfield network (CHN) is based on an energy or Lyapunov function that decreases as the system evolves until a local minimum value is attained. This approach is extended in to optimization problems with quadratic constraints. As a particular case, the graph coloring problem (GCP) is analyzed. The mapping procedure and an appropriate parameter-setting procedure are detailed. To test the theoretical results, some computational experiments solving the GCP are shown.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

A special case of the Stahl conjecture

Let _Gn,k$G_{n,k}$ denote the Kneser graph whose vertices are the n$n$-element subsets of a (2n+k)$(2n+k)$-element set and whose edges are the disjoint pairs. In this paper we prove that for any non-negative integer s$s$ there is no graph homomorphism from _G4,2$G_{4,2}$ to _G4s+1,2s+1$G_{4s+1,2s+1}$. This confirms a conjecture of Stahl in a special case.     

Robust balancing of straight assembly lines with interval task times

This paper addresses the balancing problem for straight assembly lines where task times are not known exactly but given by intervals of their possible values. The objective is to assign the tasks to workstations minimizing the number of workstations while respecting precedence and cycle-time constraints. An adaptable robust optimization model is proposed to hedge against the worst-case scenario for task times. To find the optimal solution(s), a breadth-first search procedure is developed and evaluated on benchmark instances. The results obtained are analysed and some practical recommendations are given.     

A special case of positivity (II)

In this note we prove the following special case of Serre's conjecture on Intersection Multiplicity: Let be a regular local ring and let , be two prime ideals such that , and dimension of . Then ; here denotes the Hilbert-Samuel multiplicity for any finitely generated module with respect to .

     

A special case of mahler’s conjecture

A special case of Mahler's conjecture on the volume-product of symmetric convex bodies in n -dimensional Euclidean space is treated here. This is the case of polytopes with at most 2n+2 vertices (or facets). Mahler's conjecture is proved in this case for n≤ 8 and the minimal bodies are characterized. <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p163.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received May 28, 1996, and in revised form November 7, 1996.     

A well-solvable special case of the bounded knapsack problem

We identify a polynomially solvable special case of the bounded knapsack problem that is characterized by a set of simple inequalities relating item weight ratios to item profit ratios. Our result generalizes and extends a corresponding result of Zukerman, et al. [M. Zukerman, L. Jia, T. Neame, G.J. Woeginger, A polynomially solvable special case of the unbounded knapsack problem, Operations Research Letters 29 (2001) 13-16] for the unbounded knapsack problem.     

Boolean approach to planar embeddings of a graph

The purpose of this paper which is a sequel of “ Boolean planarity characterization of graphs ” [9] is to show the following results.

1. Both of the problems of testing the planarity of graphs and embedding a planar graph into the plane are equivalent to finding a spanning tree in another graph whose order and size are bounded by a linear function of the order and the size of the original graph, respectively.
2. The number of topologically non-equivalent planar embeddings of a Hamiltonian planar graphG is τ(G)=2 ^c(H)?1, wherec (H) is the number of the components of the graphH which is related toG.