ON ASSOCIATIVE SHORTEST PATH PROBLEMS - Collections

＜journal article＞
ON ASSOCIATIVE SHORTEST PATH PROBLEMS

Creator	Creator Name Maruyama, Yukihiro 丸山, 幸宏 Affiliation Affiliation Name Department of Mathematics, Faculty of Liberal Arts, Nagasaki University 長崎大学教養部
Language	English
Publisher	Research Association of Statistical Sciences
Publisher	統計科学研究会
Date	1997-03
Source Title	Bulletin of informatics and cybernetics
Vol	29
Issue	1
First Page	67
Last Page	81
Publication Type	Version of Record
Access Rights	open access
Crossref DOI	https://doi.org/10.5109/13462
Related DOI	Bulletin of informatics and cybernetics \|\| 29(1) \|\| p67-81
Related DOI	http://bic.math.kyushu-u.ac.jp/
Related URI	Bulletin of informatics and cybernetics \|\| 29(1) \|\| p67-81
Related URI	http://bic.math.kyushu-u.ac.jp/
Relation	Bulletin of informatics and cybernetics \|\| 29(1) \|\| p67-81
Relation	http://bic.math.kyushu-u.ac.jp/
Abstract	We consider a wide class of shortest path problems in acyclic digraphs. In the problems, the length of a path is defined by using an associative binary operation. We derive recursive equations in dyna...mic programming for the problems, which involve additive, multiplicative, multiplicative-additive, minimum and fractional shortest path problems. A necessary and sufficient condition and two sufficient conditions for the recursive equation to have a solution are given because for all problems the recursive equation does not hold. In case the equation has a solution, a sequence which converges to the solution is proposed.show more

File	FileType	Size	Views	Description
p067	pdf	573 KB	378

PISSN	0286-522X
EISSN	2435-743X
NCID	AA10634475
Record ID	13462
Peer-Reviewed	Refereed
Subject Terms	acyclic digraphs
	associative binary operation
	directed network
	shortest path problems
Type	学術雑誌論文
Created Date	2009.04.22
Modified Date	2020.10.22