1. Электронный научный архив УрФУ
  2. 00. Общеуниверситетские коллекции
  3. Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/102488
Полная запись метаданных
Поле DCЗначениеЯзык
dc.contributor.authorAlam, Md. J.en
dc.contributor.authorChaplick, S.en
dc.contributor.authorFijavž, G.en
dc.contributor.authorKaufmann, M.en
dc.contributor.authorKobourov, S. G.en
dc.contributor.authorPupyrev, S.en
dc.date.accessioned2021-08-31T15:03:51Z-
dc.date.available2021-08-31T15:03:51Z-
dc.date.issued2013-
dc.identifier.citationThreshold-coloring and unit-cube contact representation of graphs / Md. J. Alam, S. Chaplick, G. Fijavž, et al. — DOI 10.1007/978-3-642-45043-3_4 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2013. — Vol. 8165 LNCS. — P. 26-37.en
dc.identifier.isbn9783642450426-
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-84893032513&doi=10.1007%2f978-3-642-45043-3_4&partnerID=40&md5=02116eb3d7bb71279eb7ef180b1631ce
dc.identifier.otherhttp://arxiv.org/pdf/1302.6183m
dc.identifier.urihttp://elar.urfu.ru/handle/10995/102488-
dc.description.abstractWe study threshold coloring of graphs where the vertex colors, represented by integers, describe any spanning subgraph of the given graph as follows. Pairs of vertices with near colors imply the edge between them is present and pairs of vertices with far colors imply the edge is absent. Not all planar graphs are threshold-colorable, but several subclasses, such as trees, some planar grids, and planar graphs with no short cycles can always be threshold-colored. Using these results we obtain unit-cube contact representation of several subclasses of planar graphs. We show the NP-completeness for two variants of the threshold coloring problem and describe a polynomial-time algorithm for another. © 2013 Springer-Verlag.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.publisherSpringer Verlagen
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.subjectALGORITHMSen
dc.subjectCOLORen
dc.subjectCOMPUTER SCIENCEen
dc.subjectGRAPHIC METHODSen
dc.subjectCOLORING PROBLEMSen
dc.subjectNP-COMPLETENESSen
dc.subjectPLANAR GRAPHen
dc.subjectPLANAR GRIDSen
dc.subjectPOLYNOMIAL-TIME ALGORITHMSen
dc.subjectREPRESENTATION OF GRAPHSen
dc.subjectSHORT CYCLEen
dc.subjectSUBGRAPHSen
dc.subjectGRAPH THEORYen
dc.titleThreshold-coloring and unit-cube contact representation of graphsen
dc.typeConference Paperen
dc.typeinfo:eu-repo/semantics/conferenceObjecten
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.identifier.doi10.1007/978-3-642-45043-3_4-
dc.identifier.scopus84893032513-
local.contributor.employeeAlam, Md.J., Department of Computer Science, University of Arizona, Tucson, AZ, United States
local.contributor.employeeChaplick, S., Department of Applied Mathematics, Charles University, Prague, Czech Republic
local.contributor.employeeFijavž, G., Faculty of Computer and Information Science, University of Ljubljana, Slovenia
local.contributor.employeeKaufmann, M., Wilhelm-Schickhard-Institut für Informatik, Universität Tübingen, Tübingen, Germany
local.contributor.employeeKobourov, S.G., Department of Computer Science, University of Arizona, Tucson, AZ, United States
local.contributor.employeePupyrev, S., Department of Computer Science, University of Arizona, Tucson, AZ, United States, Institute of Mathematics and Computer Science, Ural Federal University, Russian Federation
local.description.firstpage26-
local.description.lastpage37-
local.volume8165 LNCS-
local.contributor.departmentDepartment of Computer Science, University of Arizona, Tucson, AZ, United States
local.contributor.departmentDepartment of Applied Mathematics, Charles University, Prague, Czech Republic
local.contributor.departmentFaculty of Computer and Information Science, University of Ljubljana, Slovenia
local.contributor.departmentWilhelm-Schickhard-Institut für Informatik, Universität Tübingen, Tübingen, Germany
local.contributor.departmentInstitute of Mathematics and Computer Science, Ural Federal University, Russian Federation
local.identifier.pure880694-
local.identifier.pure1be444f8-8402-4aca-890d-3ca75524818euuid
local.identifier.eid2-s2.0-84893032513-
Располагается в коллекциях:Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

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





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