Decomposing complete tripartite graphs into cycles of lengths 3 and 4

Necessary and sufficient conditions are given for the edge-disjoint decomposition of a complete tripartite graph K-r,K-s,K-t into exactly alpha 3-cycles and beta 4-cycles. (C) 1999 Elsevier Science B.V. All rights reserved.

Maximal sets of Hamilton cycles in Kn,n

In this article, we prove that there exists a maximal set of m Hamilton cycles in K-n,K-n if and only if n/4 < m less than or equal to n/2. (C) 2000 John Wiley & Sons, Inc.

Maximum packings of K-v-K-u with triples

We construct, for all positive integers u, and v with u less than or equal to v, a decomposition of K-v - K-u (the complete graph on v vertices with a. hole of size u) into the maximum possible number of edge disjoint triangles.

Decompositions of complete multipartite graphs into cycles of even length

Necessary and sufficient conditions for the existence of an edge-disjoint decomposition of any complete multipartite graph into even length cycles are investigated. Necessary conditions are listed and sufficiency is shown for the cases when the cycle length is 4, 6 or 8. Further results concerning sufficiency, provided certain small decompositions exist, are also given for arbitrary even cycle lengths.

A family of perfect factorisations of complete bipartite graphs

A 1-factorisation of a graph is perfect if the union of any two of its 1-factors is a Hamiltonian cycle. Let n = p(2) for an odd prime p. We construct a family of (p-1)/2 non-isomorphic perfect 1-factorisations of K-n,K-n. Equivalently, we construct pan-Hamiltonian Latin squares of order n. A Latin square is pan-Hamiltoilian if the permutation defined by any row relative to any other row is a single Cycle. (C) 2002 Elsevier Science (USA).

C4-saturated bipartite graphs

Let H be a graph. A graph G is said to be H-free if it contains no subgraph isomorphic to H. A graph G is said to be an H-saturated subgraph of a graph K if G is an H-free subgraph of K with the property that for any edge e is an element of E(K)\E(G), G boolean OR {e} is not H-free. We present some general results on K-s,K-t-saturated subgraphs of the complete bipartite graph K-m,K-n and study the problem of finding, for all possible values of q, a C-4-saturated subgraph of K., having precisely q edges. (C) 2002 Elsevier Science B.V. All rights reserved.

A comparative study of similarity measures for manufacturing cell formation

We introduced a spectral clustering algorithm based on the bipartite graph model for the Manufacturing Cell Formation problem in [Oliveira S, Ribeiro JFF, Seok SC. A spectral clustering algorithm for manufacturing cell formation. Computers and Industrial Engineering. 2007 [submitted for publication]]. It constructs two similarity matrices; one for parts and one for machines. The algorithm executes a spectral clustering algorithm on each separately to find families of parts and cells of machines. The similarity measure in the approach utilized limited information between parts and between machines. This paper reviews several well-known similarity measures which have been used for Group Technology. Computational clustering results are compared by various performance measures. (C) 2008 The Society of Manufacturing Engineers. Published by Elsevier Ltd. All rights reserved.

A spectral clustering algorithm for manufacturing cell formation

A graph clustering algorithm constructs groups of closely related parts and machines separately. After they are matched for the least intercell moves, a refining process runs on the initial cell formation to decrease the number of intercell moves. A simple modification of this main approach can deal with some practical constraints, such as the popular constraint of bounding the maximum number of machines in a cell. Our approach makes a big improvement in the computational time. More importantly, improvement is seen in the number of intercell moves when the computational results were compared with best known solutions from the literature. (C) 2009 Elsevier Ltd. All rights reserved.

Icelandic Control Really Is A-Movement: Reply to Bobaljik and Landau

This article discusses the challenges that Bobaljik and Landau (2009) pose to Boeckx and Hornstein`s (2006) movement-based analysis of control in Icelandic. We show in detail that contrary to what Bobaljik and Landau claim, the movement theory of control (with a modification to accommodate quirky Case, a specialty of Icelandic) makes the right empirical cuts regarding the issues they raise, namely, (a) the differences in Case agreement between control and raising constructions, (b) the different patterns of Case transmission (un)available, and (c) the fact that allegedly Case-marked PROs are phonetically null. We argue that rather than being problematic, the data bearing on these issues actually provide independent support to the movement theory of control.

Trade spectrum of K4-e

A K-4 - e trade consists of two disjoint decompositions of some simple graph H into copies of K-4 - e. The number of vertices of H is referred to as the foundation of the trade, while the number of copies of K-4 - e in each of the decompositions is called the volume of the trade. We determine the values of v and s for which there exists a K-4 - e trade of volume s and foundation v.

A family of perfect hashing methods

Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating order preserving minimal perfect hash functions. We show that almost all members of the family construct space and time optimal order preserving minimal perfect hash functions, and we identify the one with minimum constants. Members of the family generate a hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect hash function. We give strong theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known method for generating perfect hash functions.

On the spectrum for K_{m+2}/K_m designs

The spectrum problem for the decomposition of K-n into copies of the graph K_{m+2}\K_m is solved for n = 0 or 1 (mod 2m + 1). (C) 1997 John Wiley & Sons, Inc.

The intersection problem for K_4-e designs

A G-design of order n is a pair (P,B) where P is the vertex set of the complete graph K-n and B is an edge-disjoint decomposition of K-n into copies of the simple graph G. Following design terminology, we call these copies ''blocks''. Here K-4 - e denotes the complete graph K-4 with one edge removed. It is well-known that a K-4 - e design of order n exists if and only if n = 0 or 1 (mod 5), n greater than or equal to 6. The intersection problem here asks for which k is it possible to find two K-4 - e designs (P,B-1) and (P,B-2) of order n, with \B-1 boolean AND B-2\ = k, that is, with precisely k common blocks. Here we completely solve this intersection problem for K-4 - e designs.

d-cube decompositions of K-n/K-m

Necessary conditions on n, m and d are given for the existence of an edge-disjoint decomposition of K-n\K-m into copies of the graph of a d-dimensional cube. Sufficiency is shown when d = 3 and, in some cases, when d = 2(t). We settle the problem of embedding 3-cube decompositions of K-m into 3-cube decompositions of K-n; where n greater than or equal to m.