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

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 期刊論文 > Item 987654321/29156

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/29156

题名:	Solving the all-pairs-shortest-length problem on chordal bipartite graphs
作者:	Ho,CW;Chang,JM
贡献者:	資訊工程研究所
关键词:	PATH PROBLEM;MATRICES;ALGORITHMS
日期:	1999
上传时间:	2010-06-29 20:15:03 (UTC+8)
出版者:	中央大學
摘要:	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.
關聯:	INFORMATION PROCESSING LETTERS
显示于类别:	[資訊工程研究所] 期刊論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	384	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing