Many distances in planar graphs

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Many distances in planar graphs
Authors:	ID Cabello, Sergio (Author)
Files:	http://www.imfm.si/preprinti/PDF/01089.pdf
Language:	English
Work type:	Not categorized
Organization:	FNM - Faculty of Natural Sciences and Mathematics
Abstract:	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.
Keywords:	matematika, teorija grafov, ravninski graf, razdalja, mathematics, graph theory, planar graph, distance
Year of publishing:	2009
Number of pages:	str. 1-18
Numbering:	Vol. 47, št. 1089
PID:	20.500.12556/DKUM-51785
ISSN:	1318-4865
UDC:	519.17
COBISS.SI-ID:	15142233
NUK URN:	URN:SI:UM:DK:HBH2ZYTR
Publication date in DKUM:	10.07.2015
Views:	1402
Downloads:	78
Metadata:
Categories:	Misc.
:	CABELLO, Sergio, 2009, Many distances in planar graphs [online]. 2009. [Accessed 16 March 2025]. Retrieved from: http://www.imfm.si/preprinti/PDF/01089.pdf Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Similar works from other repositories:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back