Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/102043
Полная запись метаданных
Поле DC | Значение | Язык |
---|---|---|
dc.contributor.author | Kobylkin, K. | en |
dc.date.accessioned | 2021-08-31T15:01:30Z | - |
dc.date.available | 2021-08-31T15:01:30Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | Kobylkin K. Stabbing line segments with disks: Complexity and approximation algorithms / K. Kobylkin. — DOI 10.1007/978-3-319-73013-4_33 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2018. — Vol. 10716 LNCS. — P. 356-367. | en |
dc.identifier.isbn | 9783319730127 | - |
dc.identifier.issn | 3029743 | - |
dc.identifier.other | Final | 2 |
dc.identifier.other | All Open Access, Green | 3 |
dc.identifier.other | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85039436237&doi=10.1007%2f978-3-319-73013-4_33&partnerID=40&md5=8ea5c3780c24414c08e530a3e89ad6c9 | |
dc.identifier.other | http://arxiv.org/pdf/1605.00313 | m |
dc.identifier.uri | http://elar.urfu.ru/handle/10995/102043 | - |
dc.description.abstract | Computational complexity and approximation algorithms are reported for a problem of stabbing a set of straight line segments with the least cardinality set of disks of fixed radii r> 0 where the set of segments forms a straight line drawing G= (V, E) of a planar graph without edge crossings. Close geometric problems arise in network security applications. We give strong NP-hardness of the problem for edge sets of Delaunay triangulations, Gabriel graphs and other subgraphs (which are often used in network design) for r∈ [ dmin, ηdmax] and some constant η where dmax and dmin are Euclidean lengths of the longest and shortest graph edges respectively. Fast O(|E| log |E|) -time O(1)-approximation algorithm is proposed within the class of straight line drawings of planar graphs for which the inequality r≥ ηdmax holds uniformly for some constant η> 0, i.e. when lengths of edges of G are uniformly bounded from above by some linear function of r. © Springer International Publishing AG 2018. | en |
dc.format.mimetype | application/pdf | en |
dc.language.iso | en | en |
dc.publisher | Springer Verlag | en |
dc.rights | info:eu-repo/semantics/openAccess | en |
dc.source | Lect. Notes Comput. Sci. | 2 |
dc.source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en |
dc.subject | APPROXIMATION ALGORITHMS | en |
dc.subject | COMPUTATIONAL COMPLEXITY | en |
dc.subject | CONTINUOUS DISK COVER | en |
dc.subject | DELAUNAY TRIANGULATIONS | en |
dc.subject | HITTING SET | en |
dc.subject | COMPLEX NETWORKS | en |
dc.subject | COMPUTATIONAL COMPLEXITY | en |
dc.subject | DRAWING (GRAPHICS) | en |
dc.subject | GRAPH THEORY | en |
dc.subject | GRAPHIC METHODS | en |
dc.subject | IMAGE ANALYSIS | en |
dc.subject | NETWORK SECURITY | en |
dc.subject | SURVEYING | en |
dc.subject | TRIANGULATION | en |
dc.subject | CONTINUOUS DISK COVER | en |
dc.subject | DELAU-NAY TRIANGULATIONS | en |
dc.subject | GEOMETRIC PROBLEMS | en |
dc.subject | HITTING SETS | en |
dc.subject | SECURITY APPLICATION | en |
dc.subject | STRAIGHT-LINE DRAWINGS | en |
dc.subject | STRAIGHT-LINE SEGMENTS | en |
dc.subject | UNIFORMLY BOUNDED | en |
dc.subject | APPROXIMATION ALGORITHMS | en |
dc.title | Stabbing line segments with disks: Complexity and approximation algorithms | en |
dc.type | Conference Paper | en |
dc.type | info:eu-repo/semantics/conferenceObject | en |
dc.type | info:eu-repo/semantics/publishedVersion | en |
dc.identifier.rsi | 35496262 | - |
dc.identifier.doi | 10.1007/978-3-319-73013-4_33 | - |
dc.identifier.scopus | 85039436237 | - |
local.contributor.employee | Kobylkin, K., Institute of Mathematics and Mechanics, Ural Branch of RAS, Sophya Kovalevskaya str. 16, Ekaterinburg, 620990, Russian Federation, Ural Federal University, Mira str. 19, Ekaterinburg, 620002, Russian Federation | |
local.description.firstpage | 356 | - |
local.description.lastpage | 367 | - |
local.volume | 10716 LNCS | - |
dc.identifier.wos | 000441461800033 | - |
local.contributor.department | Institute of Mathematics and Mechanics, Ural Branch of RAS, Sophya Kovalevskaya str. 16, Ekaterinburg, 620990, Russian Federation | |
local.contributor.department | Ural Federal University, Mira str. 19, Ekaterinburg, 620002, Russian Federation | |
local.identifier.pure | ff473cd7-21ca-4472-980e-cfb699c2ed39 | uuid |
local.identifier.pure | 6254840 | - |
local.identifier.eid | 2-s2.0-85039436237 | - |
local.identifier.wos | WOS:000441461800033 | - |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-85039436237.pdf | 195,97 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.