Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time

Christian Wulff-Nilsen

Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time

Bidragets oversatte titel: Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time

Datalogisk Institut

Abstract

Lad P være en korteste vej fra en knude s til en knude t i en graf G med ikke-negative kantvægte. Vi betragter følgende problem: for hver kant e på P, bestem længden af en korteste vej i G fra s til t, der undgår e. Dette er kendt som replacement paths-problemet. Vi giver en algoritme med O(nlog n) køretid og O(n) pladsforbrug for planare orienterede grafer, hvor n er antallet af knuder. Dette er en forbedring af en tidligere O(n(log n)^2)-tids-algoritme.

Bidragets oversatte titel	Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time
Originalsprog	Engelsk
Udgivelsessted	København
Udgiver	Datalogisk Institut
Sider	1-21
Antal sider	21
Status	Udgivet - 2009

Adgang til dokumentet

http://diku.dk/hjemmesider/ansatte/koolooz/09-03.pdf

Citationsformater

@techreport{026551d065a411de8bc9000ea68e967b,

title = "Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time",

abstract = "In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linear-space algorithm with O(nlog n) running time for n-vertex planar directed graphs. The previous best time bound was O(n(log n)^2).",

author = "Christian Wulff-Nilsen",

year = "2009",

language = "English",

pages = "1--21",

publisher = "Datalogisk Institut",

type = "WorkingPaper",

institution = "Datalogisk Institut",

}

TY - UNPB

T1 - Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time

AU - Wulff-Nilsen, Christian

PY - 2009

Y1 - 2009

N2 - In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linear-space algorithm with O(nlog n) running time for n-vertex planar directed graphs. The previous best time bound was O(n(log n)^2).

AB - In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linear-space algorithm with O(nlog n) running time for n-vertex planar directed graphs. The previous best time bound was O(n(log n)^2).

M3 - Working paper

SP - 1

EP - 21

BT - Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time

PB - Datalogisk Institut

CY - København

ER -

Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater