A1 Refereed original research article in a scientific journal
Embedding linear orders in grids
Authors: Ehrenfeucht A, Harju T, Rozenberg G
Publisher: SPRINGER
Publication year: 2006
Journal:Acta Informatica
Journal name in sourceACTA INFORMATICA
Journal acronym: ACTA INFORM
Volume: 42
Issue: 6-7
First page : 419
Last page: 428
Number of pages: 10
ISSN: 0001-5903
DOI: https://doi.org/10.1007/s00236-005-0001-9
Abstract
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.
UTU Research Portal