Lattice embeddings of trees

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Angleški jezik
Leto izida:	2009
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.173
COBISS:	15146841
ISSN:	0195-6698
Št. ogledov:	62
Št. prenosov:	21
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Mrežne vložitve dreves
Sekundarni povzetek:	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.
Sekundarne ključne besede:	matematika;teorija grafov;drevo;izometrična vložitev;mrežna vložitev;delna kocka;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1142-1148
Letnik:	ǂVol. ǂ30
Zvezek:	ǂno. ǂ5
Čas izdaje:	2009
ID:	1474269