Optimal embedding of a toroidal mesh in a path

Paterson, Michael S.; Schröder, Heiko; Sýkora, Ondrej; Vrto, Imrich

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Report

Optimal embedding of a toroidal mesh in a path

MPS-Authors

Paterson, Michael S.
Programming Logics, MPI for Informatics, Max Planck Society;

Schröder, Heiko
Programming Logics, MPI for Informatics, Max Planck Society;

Sýkora, Ondrej
Programming Logics, MPI for Informatics, Max Planck Society;

Vrto, Imrich
Programming Logics, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

MPI-I-91-126.pdf
(Any fulltext), 21MB

Supplementary Material (public)

There is no public supplementary material available

Citation

Paterson, M. S., Schröder, H., Sýkora, O., & Vrto, I.(1991). Optimal embedding of a toroidal mesh in a path (MPI-I-91-126). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B6DE-2

Abstract

We prove that the dilation of an $m \times n$ toroidal mesh in an $mn$-vertex path equals $2\min\{m,n\}$, if $m\not= n$ and $2n-1$, if $m=n$.