On a negative-equivalency theorem in associative optimal path problems

Autor:	Yukihiro Maruyama
Rok vydání:	2000
Předmět:	Discrete mathematics Control and Optimization Applied Mathematics Management Science and Operations Research Longest path problem Combinatorics Widest path problem Path length Binary operation Shortest path problem Path (graph theory) Canadian traveller problem Associative property Mathematics
Zdroj:	Optimization. 48:137-155
ISSN:	1029-4945 0233-1934
DOI:	10.1080/02331930008844498
Popis:	In this we study a wide class of optimal path problem in acyclic digraphs, where path lengths are defined through associative binary operations:addition, multiplication, multiplication-addition, fraction and so on. Solving a system of two interrelated recur-sive equations, we simultaneously find both shortest and longest path lengths, Further, for every problem (primal problem), we associate the other related problem (negative-equivalent problem) where each path length is defined through the associative operation connected to it in the primal problem by DeMorgan’s law. The main objective of this paper is to derive a negative-equivalency theorem between the primal problem and the negative-equivalent one
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::4c8613fede19825e75f705d40fa6a599 https://doi.org/10.1080/02331930008844498 Zobrazit plný text záznamu