1. Электронный научный архив УрФУ
  2. 00. Общеуниверситетские коллекции
  3. Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/92722
Полная запись метаданных
Поле DCЗначениеЯзык
dc.contributor.authorChentsov, A.en
dc.contributor.authorKhachay, M.en
dc.contributor.authorKhachay, D.en
dc.date.accessioned2020-10-20T16:36:55Z-
dc.date.available2020-10-20T16:36:55Z-
dc.date.issued2016-
dc.identifier.citationChentsov A. Linear time algorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problem / A. Chentsov, M. Khachay, D. Khachay. — DOI 10.1016/j.ifacol.2016.07.767 // IFAC-PapersOnLine. — 2016. — Vol. 12. — Iss. 49. — P. 651-655.en
dc.identifier.issn2405-8963-
dc.identifier.otherhttps://doi.org/10.1016/j.ifacol.2016.07.767pdf
dc.identifier.other1good_DOI
dc.identifier.other3ee59682-0bfc-4815-a7b6-4152bf18f36bpure_uuid
dc.identifier.otherhttp://www.scopus.com/inward/record.url?partnerID=8YFLogxK&scp=84992365688m
dc.identifier.urihttp://elar.urfu.ru/handle/10995/92722-
dc.description.abstractWe consider the combinatorial optimization problem of visiting clusters of a fixed number of nodes (cities), where, on the set of clusters should be visited according to some kind of partial order defined by additional precedence constraints. This problem is a kind of the Asymmetric Generalized Traveling Salesman Problem (AGTSP). To find an optimal solution of the problem, we propose a dynamic programming based on algorithm extending the well known Held and Karp technique. In terms of special type of precedence constraints, we describe subclasses of the problem, with polynomial (or even linear) in n upper bounds of time complexity. © 2016en
dc.description.sponsorshipRussian Science Foundation, RSF: 14-11-00109en
dc.description.sponsorshipThis research was supported by the Russian Science Foundation, grant No. 14-11-00109.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.publisherElsevier B.V.en
dc.relationinfo:eu-repo/grantAgreement/RSF//14-11-00109en
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceIFAC-PapersOnLineen
dc.subjectASYMMETRIC GENERALIZED TRAVELING SALESMAN PROBLEM (AGTSP)en
dc.subjectDYNAMIC PROGRAMMINGen
dc.subjectNP-HARD PROBLEMen
dc.subjectCLUSTERING ALGORITHMSen
dc.subjectCOMBINATORIAL OPTIMIZATIONen
dc.subjectCOMPUTATIONAL COMPLEXITYen
dc.subjectDYNAMIC PROGRAMMINGen
dc.subjectOPTIMIZATIONen
dc.subjectCOMBINATORIAL OPTIMIZATION PROBLEMSen
dc.subjectFIXED NUMBERSen
dc.subjectGENERALIZED TRAVELING SALESMAN PROBLEMen
dc.subjectLINEAR-TIME ALGORITHMSen
dc.subjectOPTIMAL SOLUTIONSen
dc.subjectPARTIAL ORDERen
dc.subjectPRECEDENCE CONSTRAINTSen
dc.subjectTIME COMPLEXITYen
dc.subjectTRAVELING SALESMAN PROBLEMen
dc.titleLinear time algorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problemen
dc.typeArticleen
dc.typeinfo:eu-repo/semantics/articleen
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.identifier.doi10.1016/j.ifacol.2016.07.767-
dc.identifier.scopus84992365688-
local.affiliationKrasovsky Institute of Mathematics and Mechanics, Ural Federal University, 16 S.Kovalevskoy str., 19 Mira str, Ekaterinburg, 620990, Russian Federation
local.contributor.employeeChentsov, A., Krasovsky Institute of Mathematics and Mechanics, Ural Federal University, 16 S.Kovalevskoy str., 19 Mira str, Ekaterinburg, 620990, Russian Federation
local.contributor.employeeKhachay, M., Krasovsky Institute of Mathematics and Mechanics, Ural Federal University, 16 S.Kovalevskoy str., 19 Mira str, Ekaterinburg, 620990, Russian Federation
local.contributor.employeeKhachay, D., Krasovsky Institute of Mathematics and Mechanics, Ural Federal University, 16 S.Kovalevskoy str., 19 Mira str, Ekaterinburg, 620990, Russian Federation
local.description.firstpage651-
local.description.lastpage655-
local.issue49-
local.volume12-
dc.identifier.wos000383468400112-
local.identifier.pure1189568-
local.identifier.eid2-s2.0-84992365688-
local.fund.rsf14-11-00109-
local.identifier.wosWOS:000383468400112-
Располагается в коллекциях:Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
10.1016-j.ifacol.2016.07.767.pdf419,64 kBAdobe PDFПросмотреть/Открыть
Показать базовое описание ресурса Статистика


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.