Upper Bounds on the Covering Number of Galois-planes with Small Order

Tibor Illes, Pisinger D

Research output: Book/ReportBook

Abstract

Our paper deals with a problem of P. Erdős' related to the covering number of blocking sets of finite projective planes. An integer linear programming (ILP) formulation of Erdős' problem is introduced for projective planes of given orders. The mathematical programming based approach for this problem is new in the area of finite projective planes. Since the ILP problem is NP-hard and may involve up to 360.000 boolean variables for the considered problems, we propose a heuristic based on simulated annealing. The computational study gives a new insight into the structure of projective planes and their (minimal) blocking sets. This computational study indicates that the current theoretical results may be improved.
Original languageEnglish
Place of PublicationCopenhagen
Number of pages16
Publication statusPublished - 1997

Keywords

  • Galois-plane
  • blocking sets
  • 0-1 programming
  • simulated annealing

Fingerprint Dive into the research topics of 'Upper Bounds on the Covering Number of Galois-planes with Small Order'. Together they form a unique fingerprint.

  • Cite this