Presentation	2010-12-17 A proposal of k shortest simple path algorithm to minimize computational complexity Hiroshi MATSUURA,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	k shortest path algorithm is expected to be applied to creating replacement paths and traffic dispersion by using multiple paths on a network, k shortest simple path algorithm, which creates loopless k shortest paths, on the directed graph has been researched as long as 50 years, and its shortest computational complexity so far is O(knm), where n is the number of nodes and m is the number of links. In this paper, our new proposed k shortest simple path algorithm named k-SPF shortens the computational complexity to O(km (log n + log k)). We also implemented k-SPF and conventional Yen algorithm and compares their processing times.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	k shortest path algorithm / Binary search tree / Fibonacci heaps / Computational complexity
Paper #	IN2010-107
Date of Issue

Conference Information
Committee	IN
Conference Date	2010/12/9(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Information Networks (IN)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	A proposal of k shortest simple path algorithm to minimize computational complexity
Sub Title (in English)
Keyword(1)	k shortest path algorithm
Keyword(2)	Binary search tree
Keyword(3)	Fibonacci heaps
Keyword(4)	Computational complexity
1st Author's Name	Hiroshi MATSUURA
1st Author's Affiliation	NTT Service Integration Laboratories, NIPPON TELEGRAPH AND TELEPHONE CORPORATION()
Date	2010-12-17
Paper #	IN2010-107
Volume (vol)	vol.110
Number (no)	341
Page	pp.pp.-
#Pages	6
Date of Issue