In this paper we propose an algorithm for enumerating diagonal Latin squares of small order. It relies on specific properties of diagonal Latin squares to employ symmetry breaking techniques, and on several heuristic optimizations and bit arithmetic techniques to make use of computational power of state-of-the-art CPUs. Using this approach we enumerated diagonal Latin squares of order at most 9, and vertically symmetric diagonal Latin squares of order at most 10.
Authors are not aware of algorithms developed specifically for enumeration of diagonal Latin squares. Papers @cite_8 @cite_12 @cite_6 describe the approaches that led to enumeration of Latin squares of orders 9, 10 and 11. The corresponding algorithms heavily rely on the ability to permute rows and columns to construct equivalence classes and evaluate their properties. To the best of our knowledge the results of these papers are not applicable to diagonal Latin squares because the vast majority of row-column permutations break diagonal property. Also, diagonal Latin squares form relatively small equivalence classes.
@cite_6 @cite_12 @cite_8
2069392999 2116878278 2400716891 2035173902
We (1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares of order 11, (2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f! where f is a particular integer close to ( 1 2 n, ) (3) provide a formula for the number of Latin squares in terms of permanents of (+1, −1)-matrices, (4) find the extremal values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever 1 ≤ k ≤ n ≤ 11, (5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order increases. In this paper we apply multilabel classification algorithms to the EUR-Lex database of legal documents of the European Union. For this document collection, we studied three different multilabel classification problems, the largest being the categorization into the EUROVOC concept hierarchy with almost 4000 classes. We evaluated three algorithms: (i) the binary relevance approach which independently trains one classifier per label; (ii) the multiclass multilabel perceptron algorithm, which respects dependencies between the base classifiers; and (iii) the multilabel pairwise perceptron algorithm, which trains one classifier for each pair of labels. All algorithms use the simple but very efficient perceptron algorithm as the underlying classifier, which makes them very suitable for large-scale multilabel classification problems. The main challenge we had to face was that the almost 8,000,000 perceptrons that had to be trained in the pairwise setting could no longer be stored in memory. We solve this problem by resorting to the dual representation of the perceptron, which makes the pairwise approach feasible for problems of this size. The results on the EUR-Lex database confirm the good predictive performance of the pairwise approach and demonstrates the feasibility of this approach for large-scale tasks. While there has been significant progress on algorithmic aspects of the Lovasz Local Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context of random permutations: the "lopsided" version of the LLL is usually at play here, and we do not yet have subexponential-time algorithms. We resolve this by developing a randomized polynomial-time algorithm for such applications. A noteworthy application is for Latin Transversals: the best-known general result here (, improving on Erdos and Spencer), states that any n x n matrix in which each entry appears at most (27 256)n times, has a Latin transversal. We present the first polynomial-time algorithm to construct such a transversal. Our approach also yields RNC algorithms: for Latin transversals, as well as the first efficient ones for the strong chromatic number and (special cases of) acyclic edge-coloring. Given a query graph q and a data graph g, the subgraph isomorphism search finds all occurrences of q in g and is considered one of the most fundamental query types for many real applications. While this problem belongs to NP-hard, many algorithms have been proposed to solve it in a reasonable time for real datasets. However, a recent study has shown, through an extensive benchmark with various real datasets, that all existing algorithms have serious problems in their matching order selection. Furthermore, all algorithms blindly permutate all possible mappings for query vertices, often leading to useless computations. In this paper, we present an efficient and robust subgraph search solution, called TurboISO, which is turbo-charged with two novel concepts, candidate region exploration and the combine and permute strategy (in short, Comb Perm). The candidate region exploration identifies on-the-fly candidate subgraphs (i.e, candidate regions), which contain embeddings, and computes a robust matching order for each candidate region explored. The Comb Perm strategy exploits the novel concept of the neighborhood equivalence class (NEC). Each query vertex in the same NEC has identically matching data vertices. During subgraph isomorphism search, Comb Perm generates only combinations for each NEC instead of permutating all possible enumerations. Thus, if a chosen combination is determined to not contribute to a complete solution, all possible permutations for that combination will be safely pruned. Extensive experiments with many real datasets show that TurboISO consistently and significantly outperforms all competitors by up to several orders of magnitude.