In the literature most counting problems for directed columnconvex polyominoes are solved by using Schutzenberger's method. In this paper, we use the traditional recurrence relation approach in order to count the number of directed column-convex polyominoes with a given area, the number of their columns and the number of directed columnconvex polyominoes having at most κ cells in the first column. This approach allows us to state a very simple algorithm for the random generation of directed column-convex polyominoes. Furthermore, directed column-convex polyominoes are considered to be structures for storing and retrieving information in a computer, and their average internal path length is then evaluated.

DIRECTED COLUMN-CONVEX POLYOMINOES BY RECURRENCE RELATIONS / E. BARCUCCI; R. PINZANI; R. SPRUGNOLI. - STAMPA. - 668:(1993), pp. 282-298. ((Intervento presentato al convegno TAPSOFT'93 [10.1007/3-540-56610-4_71].

DIRECTED COLUMN-CONVEX POLYOMINOES BY RECURRENCE RELATIONS

BARCUCCI, ELENA;PINZANI, RENZO;SPRUGNOLI, RENZO
1993

Abstract

In the literature most counting problems for directed columnconvex polyominoes are solved by using Schutzenberger's method. In this paper, we use the traditional recurrence relation approach in order to count the number of directed column-convex polyominoes with a given area, the number of their columns and the number of directed columnconvex polyominoes having at most κ cells in the first column. This approach allows us to state a very simple algorithm for the random generation of directed column-convex polyominoes. Furthermore, directed column-convex polyominoes are considered to be structures for storing and retrieving information in a computer, and their average internal path length is then evaluated.
TAPSOFT'93: Theory and Practice of Software Development
TAPSOFT'93
E. BARCUCCI; R. PINZANI; R. SPRUGNOLI
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2158/10857
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? ND
social impact