Many distances in planar graphs

Povzetek

We show how to compute in ▫$O(n^{4/3} \log^{1/3} n + n^{2/3}k^{2/3} \log n)$▫ time the distance between $k$ given pairs of vertices of a planar graph $G$ with ▫$n$▫ vertices. This improves previous results whenever ▫$(n/\log n)^{5/6} \le k \le n^2/\log^6 n$▫. As an application, we speed up previous algorithms for computing the dilation of geometric planar graphs.

Ključne besede

matematika;teorija grafov;ravninski graf;razdalja;mathematics;graph theory;planar graph;distance;

Podatki

Jezik:	Angleški jezik
Leto izida:	2009
Tipologija:	0 - Ni določena
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	15142233
ISSN:	1318-4865
Št. ogledov:	33
Št. prenosov:	7
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarne ključne besede:	matematika;teorija grafov;ravninski graf;razdalja;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1-18
Letnik:	ǂVol. ǂ47
Zvezek:	ǂšt. ǂ1089
Čas izdaje:	2009
ID:	1474262