FINDING THE K QUICKEST SIMPLE PATHS IN A NETWORK

NCUIR > School of Management at National Central University > Graduate Institute of Information Management > journal & Dissertation > Item 987654321/29695

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/29695

Title:	FINDING THE K QUICKEST SIMPLE PATHS IN A NETWORK
Authors:	CHEN,YL
Contributors:	資訊管理研究所
Keywords:	ALGORITHMS
Date:	1994
Issue Date:	2010-06-29 20:38:26 (UTC+8)
Publisher:	中央大學
Abstract:	Let N be a network with n nodes and m arcs, and let sigma be the amount of data to be transmitted. The quickest path problem is to find a routing path in N such that the time required to ship sigma units of data from the source to the sink is minimum. The problem considered in this paper is to find the first k quickest simple paths for a given pair of nodes, and an algorithm is designed. The complexity required by the proposed algorithm is O(kmn3 + kmn log k) if the network is directed and is O(kmn2 + kmn log k) if the network is undirected.
Relation:	INFORMATION PROCESSING LETTERS
Appears in Collections:	[Graduate Institute of Information Management] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	581	View/Open

社群 sharing