On the P4-structure of perfect graphs I. Even decompositions

We present easily verifiable conditions, under which a graph G contains nonempty vertex-disjoint induced subgraphs G₁, G₂ such that G is perfect if and only if G₁ and G₂ are. This decomposition is defined in terms of the induced subgraphs of G that are isomorphic to the chordless path with four vertices.     

Sylvester–Gallai Theorem and Metric Betweenness

Sylvester conjectured in 1893 and Gallai proved some 40 years later that every finite set S of points in the plane includes two points such that the line passing through them includes either no other point of S or all other points of S. There are several ways of extending the notion of lines from Euclidean spaces to arbitrary metric spaces. We present one of them and conjecture that, with lines in metric spaces defined in this way, the Sylvester--Gallai theorem generalizes as follows: in every finite metric space there is a line consisting of either two points or all the points of the space. Then we present meagre evidence in support of this rash conjecture and finally we discuss the underlying ternary relation of metric betweenness.     

Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems

 Dantzig, Fulkerson, and Johnson (1954) introduced the cutting-plane method as a means of attacking the traveling salesman problem; this method has been applied to broad classes of problems in combinatorial optimization and integer programming. In this paper we discuss an implementation of Dantzig et al.'s method that is suitable for TSP instances having 1,000,000 or more cities. Our aim is to use the study of the TSP as a step towards understanding the applicability and limits of the general cutting-plane method in large-scale applications. Received: December 6, 2002 / Accepted: April 24, 2003 Published online: May 28, 2003 RID="*" ID="*" Supported by ONR Grant N00014-03-1-0040     

Local cuts for mixed-integer programming

A general framework for cutting-plane generation was proposed by Applegate et al. in the context of the traveling salesman problem. The process considers the image of a problem space under a linear mapping, chosen so that a relaxation of the mapped problem can be solved efficiently. Optimization in the mapped space can be used to find a separating hyperplane, if one exists, and via substitution this gives a cutting plane in the original space. We extend this procedure to general mixed-integer programming problems, obtaining a range of possibilities for new sources of cutting planes. Some of these possibilities are explored computationally, both in floating-point arithmetic and in rational arithmetic.     

Star-cutsets and perfect graphs

We first establish a certain property of minimal imperfect graphs and then use it to generate large classes of perfect graphs.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).