A linear algorithm for the shortest transformation of graphs with different operation costsстатьяПереводИсследовательская статья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 3 декабря 2017 г.
Аннотация:A novel time- and memory-efficient algorithm for solving the problem of finding the most economical (i.e., having the lowest overall cost) transformation of an arbitrary oriented graph representing a disjoint union of chains and cycles into another graph of the same type is proposed. The correctness of this algorithm (i.e., the fact that it always yields the minimum of the overall cost functional) and the linearity of the estimated memory and time of its operation are demonstrated.