A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Embedding linear orders in grids
Tekijät: Ehrenfeucht A, Harju T, Rozenberg G
Kustantaja: SPRINGER
Julkaisuvuosi: 2006
Lehti: Acta Informatica
Tietokannassa oleva lehden nimi: ACTA INFORMATICA
Lehden akronyymi: ACTA INFORM
Vuosikerta: 42
Numero: 6-7
Aloitussivu: 419
Lopetussivu: 428
Sivujen määrä: 10
ISSN: 0001-5903
DOI: https://doi.org/10.1007/s00236-005-0001-9
Tiivistelmä
A grid (or a mesh) is a two-dimensional permutation: an m x n-grid of size mn is an m x n-matrix where the entries run through the elements {1,2, ..., mn}. We prove that if delta(1) and delta(2) are any two linear orders on {1,2,..., N}, then they can be simultaneously embedded (in a well defined sense) into a unique grid having the smallest size.
A grid (or a mesh) is a two-dimensional permutation: an m x n-grid of size mn is an m x n-matrix where the entries run through the elements {1,2, ..., mn}. We prove that if delta(1) and delta(2) are any two linear orders on {1,2,..., N}, then they can be simultaneously embedded (in a well defined sense) into a unique grid having the smallest size.
Turun yliopiston Tutkimustietojärjestelmän portaali