Embedding linear orders in grids |
| |
| Authors: | Andrzej Ehrenfeucht Tero Harju Grzegorz Rozenberg |
| |
| Affiliation: | (1) Department of Computer Science, University of Colorado at Boulder, Boulder, CO 80309-0347, USA;(2) Department of Mathematics, University of Turku, 20014 Turku, Finland;(3) Leiden Institute for Advanced Computer Science, Leiden University, 2333 Leiden, CA, The Netherlands |
| |
| Abstract: | A grid (or a mesh) is a two-dimensional permutation: an m× n-grid of size mn is an m× n-matrix where the entries run through the elements {1,2, …, mn}. We prove that if δ1 and δ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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
