Solution techniques for the Large Set Covering Problem

Given a finite set E and a family F={E₁,…,E_m} of subsets of E such that F covers E, the famous unicost set covering problem (USCP) is to determine the smallest possible subset of F that also covers E. We study in this paper a variant, called the Large Set Covering Problem (LSCP), which differs from the USCP in that E and the subsets E_i are not given in extension because they are very large sets that are possibly infinite. We propose three exact algorithms for solving the LSCP. Two of them determine minimal covers, while the third one produces minimum covers. Heuristic versions of these algorithms are also proposed and analysed. We then give several procedures for the computation of a lower bound on the minimum size of a cover. We finally present algorithms for finding the largest possible subset of F that does not cover E. We also show that a particular case of the LSCP is to determine irreducible infeasible sets in inconsistent constraint satisfaction problems. All concepts presented in the paper are illustrated on the k-colouring problem which is formulated as a constraint satisfaction problem.     

三角几何的基本群(英)

利用Building理论获得一种计算某些三角几何的基本群的新的方法．这种方法能够容易地计算出无限多有限三角几何的基拓扑基本群．     

准晶理论的新进展

准晶的高分辨电子显微像常显示为直径为2nm、呈十重对称的圆盘,它们还经常重叠。据此,Gummelt在1995年设计出一种内部涂有两种颜色的正十边形,并且证明只要在覆盖时两个十边形中同一颜色的部分相重,就会给出准周期的Penrose图。这种覆盖理论只需要一种正十边形的“准单胞”,覆盖部分是相邻“准单胞”生长的核。覆盖越多,结构越稳定。Gummelt在1999年将正十边形中的两种颜色去掉,既可给出准周期结构,也可给出周期结构,以及介于它们两者之间的各种中间结构。     

The Gray graph revisited

Certain graph‐theoretic properties and alternative definitions of the Gray graph, the smallest known cubic edge‐ but not vertex‐transitive graph, are discussed in detail. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 1–7, 2000     

New coverings of t-sets with (t + 1)-sets

The minimum number of k-subsets out of a v-set such that each t-set is contained in at least one k-set is denoted by C(v, k, t). In this article, a computer search for finding good such covering designs, leading to new upper bounds on C(v, k, t), is considered. The search is facilitated by predetermining automorphisms of desired covering designs. A stochastic heuristic search (embedded in the general framework of tabu search) is then used to find appropriate sets of orbits. A table of upper bounds on C(v, t + 1, t) for v 28 and t 8 is given, and the new covering designs are listed. © 1999 John Wiley & Sons, Inc. J. Combin Designs 7: 217–226, 1999     

Combinatorial coverings from geometries over principal ideal rings

A t-(v, k, λ) covering is an incidence structure with v points, each block incident on exactly k points, such that every set of t distinct points is incident on at least λ blocks. By considering certain geometries over finite principal ideal rings, we construct infinite families of t-(v, k, λ) coverings having many interesting combinatorial properties. © 1999 John & Sons, Inc. J Combin Designs 7: 247–268, 1999     

十二次对称准周期结构的自相似变换及准晶胞构造

研究十二次对称准晶体模型的几何结构性质.修正了Socolar在正方形-菱形-六边形拼图模型中自相似变换的错误.在Stampfli-Ghler正方形-菱形-三角形拼图模型的基础上,成功地构造出了准晶胞,使得十二次对称准周期结构可以用覆盖理论描述. 关键词： 准晶体 拼图模型 自相似变换 覆盖理论     

Zhang–Zhang polynomials of cyclo-polyphenacenes

The Zhang–Zhang polynomial (i.e., Clar covering polynomial) of hexagonal systems is introduced by H. Zhang and F. Zhang, which can be used to calculate many important invariants such as the Clar number, the number of Kekulé structures and the first Herndon number, etc. In this paper, we give out an explicit recurrence expression for the Zhang–Zhang polynomials of the cyclo-polyphenacenes, and determine their Clar numbers, numbers of Kekulé structures and their first Herndon numbers.     

Enumerating typical abelian prime-fold coverings of a circulant graph

Enumerating the isomorphism classes of several types of graph coverings is one of the central research topics in enumerative topological graph theory (see [R. Feng, J.H. Kwak, J. Kim, J. Lee, Isomorphism classes of concrete graph coverings, SIAM J. Discrete Math. 11 (1998) 265-272; R. Feng, J.H. Kwak, Typical circulant double coverings of a circulant graph, Discrete Math. 277 (2004) 73-85; R. Feng, J.H. Kwak, Y.S. Kwon, Enumerating typical circulant covering projections onto a circulant graph, SIAM J. Discrete Math. 19 (2005) 196-207; SIAM J. Discrete Math. 21 (2007) 548-550 (erratum); M. Hofmeister, Graph covering projections arising from finite vector spaces over finite fields, Discrete Math. 143 (1995) 87-97; M. Hofmeister, Enumeration of concrete regular covering projections, SIAM J. Discrete Math. 8 (1995) 51-61; M. Hofmeister, A note on counting connected graph covering projections, SIAM J. Discrete Math. 11 (1998) 286-292; J.H. Kwak, J. Chun, J. Lee, Enumeration of regular graph coverings having finite abelian covering transformation groups, SIAM J. Discrete Math. 11 (1998) 273-285; J.H. Kwak, J. Lee, Isomorphism classes of graph bundles, Canad. J. Math. XLII (1990) 747-761]). A covering is called abelian (or circulant, respectively) if its covering graph is a Cayley graph on an abelian (or a cyclic, respectively) group. A covering p from a Cayley graph onto another Cay (Q,Y) is called typical if the map p:A→Q on the vertex sets is a group epimorphism. Recently, the isomorphism classes of connected typical circulant r-fold coverings of a circulant graph are enumerated in [R. Feng, J.H. Kwak, Typical circulant double coverings of a circulant graph, Discrete Math. 277 (2004) 73-85] for r=2 and in [R. Feng, J.H. Kwak, Y.S. Kwon, Enumerating typical circulant covering projections onto a circulant graph, SIAM J. Discrete Math. 19 (2005) 196-207; SIAM J. Discrete Math. 21 (2007) 548-550 (erratum)] for any r. As a continuation of these works, we enumerate in this paper the isomorphism classes of typical abelian prime-fold coverings of a circulant graph.