1. Электронный научный архив УрФУ
  2. 00. Общеуниверситетские коллекции
  3. Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/102500
Полная запись метаданных
Поле DCЗначениеЯзык
dc.contributor.authorFink, M.en
dc.contributor.authorPupyrev, S.en
dc.date.accessioned2021-08-31T15:03:54Z-
dc.date.available2021-08-31T15:03:54Z-
dc.date.issued2013-
dc.identifier.citationFink M. Ordering metro lines by block crossings / M. Fink, S. Pupyrev. — DOI 10.1007/978-3-642-40313-2_36 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2013. — Vol. 8087 LNCS. — P. 397-408.en
dc.identifier.isbn9783642403125-
dc.identifier.issn3029743-
dc.identifier.otherFinal2
dc.identifier.otherAll Open Access, Green3
dc.identifier.otherhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84885209692&doi=10.1007%2f978-3-642-40313-2_36&partnerID=40&md5=cf70e4be6e9492c1263fc0b304f11d36
dc.identifier.otherhttps://elar.urfu.ru/bitstream/10995/92447/1/10.7155-jgaa.00351.pdfm
dc.identifier.urihttp://elar.urfu.ru/handle/10995/102500-
dc.description.abstractA problem that arises in drawings of transportation networks is to minimize the number of crossings between different transportation lines. While this can be done efficiently under specific constraints, not all solutions are visually equivalent. We suggest merging crossings into block crossings, that is, crossings of two neighboring groups of consecutive lines. Unfortunately, minimizing the total number of block crossings is NP-hard even for very simple graphs. We give approximation algorithms for special classes of graphs and an asymptotically worst-case optimal algorithm for block crossings on general graphs. © 2013 Springer-Verlag.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceLect. Notes Comput. Sci.2
dc.sourceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en
dc.subjectALL SOLUTIONSen
dc.subjectGENERAL GRAPHen
dc.subjectMETRO LINESen
dc.subjectNUMBER OF BLOCKSen
dc.subjectOPTIMAL ALGORITHMen
dc.subjectSPECIAL CLASSen
dc.subjectTRANSPORTATION LINEen
dc.subjectTRANSPORTATION NETWORKen
dc.subjectCOMPUTER SCIENCEen
dc.subjectAPPROXIMATION ALGORITHMSen
dc.titleOrdering metro lines by block crossingsen
dc.typeConference Paperen
dc.typeinfo:eu-repo/semantics/conferenceObjecten
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.identifier.doi10.1007/978-3-642-40313-2_36-
dc.identifier.scopus84885209692-
local.contributor.employeeFink, M., Lehrstuhl für Informatik I, Universität Würzburg, Germany
local.contributor.employeePupyrev, S., Department of Computer Science, University of Arizona, United States, Ural Federal University, Ekaterinburg, Russian Federation
local.description.firstpage397-
local.description.lastpage408-
local.volume8087 LNCS-
dc.identifier.wos000342994500036-
local.contributor.departmentLehrstuhl für Informatik I, Universität Würzburg, Germany
local.contributor.departmentDepartment of Computer Science, University of Arizona, United States
local.contributor.departmentUral Federal University, Ekaterinburg, Russian Federation
local.identifier.pure3df2c5aa-e828-48db-adf4-54b67b7172bduuid
local.identifier.pure858419-
local.identifier.eid2-s2.0-84885209692-
local.identifier.wosWOS:000342994500036-
Располагается в коллекциях:Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
2-s2.0-84885209692.pdf800,66 kBAdobe PDFПросмотреть/Открыть
Показать базовое описание ресурса Статистика


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