The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Recently R.G. Bland proposed two new rules for pivot selection in the simplex method. These elegant rules arise from Bland’s work on oriented matroids; their virtue is that they never lead to cycling. We investigate the efficiency of the first of them. On randomly generated problems with 50 nonnegative variables and 50 additional inequalities, Bland’s rule requires about 400 iterations on the average;...
A direct algorithmic procedure is described for computing Hamiltonian circuits in graphs which satisfy a condition due to Chvátal. For a graph with p vertices this procedure works in O(p3) operations. It is suggested how this procedure might be used heuristically to compute long paths in general graphs.
An algorithm for finding an optimum weight perfect matching in a graph is described. It differs from Edmonds’ “blossom” algorithm in that a perfect matching is at hand throughout the algorithm, and a feasible solution to the dual problem is obtained only at termination. In many other respects, including its efficiency, it is similar to the blossom algorithm. Some advantages of this “primal” algorithm...
Let N be a finite set and a nonempty collection of subsets of N which have the property that and F2⊂F1 imply . A real-valued function z defined on the subsets of N that satifies z(S)≤z(T) for all S⊂T⊃-N and z(S)+z(T)≥(S∪T)+z(S∩T) for all S,T⊂-N is called nondecreasing and submodular. We consider the problem , z(S) submodular and nondecreasing} and several special cases of it...
It is shown that the primal-dual algorithm for the ordinary assignment problem and for its Menger-type generalization can be extended in a natural manner to the case where both the entrance vertex set and the exit vertex set of the underlying graph are endowed with respective matroidal structures. The generalization of a Menger theorem is proved on the basis of the algorithm.
The adjacency of two vertices on an arbitrary 0–1-polyhedron P is characterized by certain criteria involving the (prime) implicants of P, which are generalizations of the circuits of an independence system. These criteria can be checked by straightforward “colouring algorithms”. They are sufficient for all 0–1-polyhedra and necessary for at least three classes containing the polyhedra of many well-known...
An easy characterization is given of neighbors on permutation polytopes. Using this characterization it is shown that the graph of any such polytope is Hamiltonian, and that the diameter is two.
Blocking and anti-blocking results of a symmetric form are derived for certain families of points related to complementary orthogonal subspaces of Rn. The relation of this material to earlier blocking and anti-blocking results for integral feasible flows in supply-demand and circulation networks and its relation to earlier blocking results for complementary orthogonal subspaces of R ...
Two new results are proved concerning polyhedra that arise as relaxations of systems of the form Ax=b, x≥0. One of these theorems is used to relate elementary vectors and blocking polyhedra. In particular, a canonical blocking pair that arises from elementary vectors is described; all blocking pairs arise as minors of blocking pairs of this type. It is noted that a similar relationship between elementary...
Conditions are given for two sets to be the level sets of a support function. Then, Fulkerson’s concepts of blocking pairs and anti-blocking pairs are generalized, and similar conditions are given for two polyhedra to be an anti-blocker and blocker of some polyhedron.
We consider two classes (called upper and lower) of clutters satisfying postulates we have previously encountered in defining lattice polyhedra, and prove that lower clutters are maximal anti-chains in a partially ordered set, upper clutters are cuts of a family of paths closed with respect to switching.
By using a basic formula concerning the adjoint of a projective transformation, it is shown how the projective structure of a face-figure of a polytope P can be described in terms of the boundary structure of P’s polar.
A 0–1 matrix is said to be equalized if the number of the 1’s in the columns differ at most by one. With the help of equalized matrices we obtain results about the edge-colouring of certain hypergraphs.
Let be a hypergraph on a set X of vertices. A multicoloring of the vertices of H in k colors is an assignment to each vertex of one or several colors so that in each edge every color occurs exactly once. In this paper, we investigate the existence of a multicoloring for the dual of a graph and for some other hypergraphs. More generally, we are interested in the structure of a hypergraph such...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.