Solving the all-pairs-shortest-length problem on chordal bipartite graphs

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > journal & Dissertation > Item 987654321/29156

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

Title:	Solving the all-pairs-shortest-length problem on chordal bipartite graphs
Authors:	Ho,CW;Chang,JM
Contributors:	資訊工程研究所
Keywords:	PATH PROBLEM;MATRICES;ALGORITHMS
Date:	1999
Issue Date:	2010-06-29 20:15:03 (UTC+8)
Publisher:	中央大學
Abstract:	The all-pairs-shortest-length (APSL) problem of a graph is to find the lengths of the shortest paths between all pairs of vertices. In this paper, we study the APSL problem on chordal bipartite graphs. By a simple reduction, we show that solving the APSL problem on chordal bipartite graphs can be transformed to solving the same problem on certain strongly chordal graphs. Consequently, there is an O(n(2)) time-optimal algorithm for this problem. (C) 1999 Elsevier Science B.V. All rights reserved.
Relation:	INFORMATION PROCESSING LETTERS
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] journal & Dissertation

Files in This Item:

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

社群 sharing