Lattice embeddings of trees

Wilfried Imrich (Author), Matjaž Kovše (Author)

Abstract

Predstavljen je algoritem časovno linearne zahtevnosti, ki na izometričen način vloži dano drevo ▫$T$▫ v celoštevilsko mrežo najmanjše možne dimenzije in omogoča izračun mrežnih koordinat vozlišč drevesa ▫$T$▫ v optimalnem času.

Keywords

matematika;teorija grafov;drevo;izometrična vložitev;mrežna vložitev;delna kocka;mathematics;graph theory;lattice embedding;isometric embedding;partial cube;tree;

Data

Language:	English
Year of publishing:	2009
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.173
COBISS:	15146841
ISSN:	0195-6698
Views:	62
Downloads:	21
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Mrežne vložitve dreves
Secondary abstract:	We present a linear algorithm that isometrically embeds a given tree ▫$T$▫ into an integer lattice of minimal dimension and allows one to compute the lattice coordinates of every single vertex of ▫$T$▫ in optimal time.
Secondary keywords:	matematika;teorija grafov;drevo;izometrična vložitev;mrežna vložitev;delna kocka;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1142-1148
Volume:	ǂVol. ǂ30
Issue:	ǂno. ǂ5
Chronology:	2009
ID:	1474269