Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102043
Title: Stabbing line segments with disks: Complexity and approximation algorithms
Authors: Kobylkin, K.
Issue Date: 2018
Publisher: Springer Verlag
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.
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.
Keywords: APPROXIMATION ALGORITHMS
COMPUTATIONAL COMPLEXITY
CONTINUOUS DISK COVER
DELAUNAY TRIANGULATIONS
HITTING SET
COMPLEX NETWORKS
COMPUTATIONAL COMPLEXITY
DRAWING (GRAPHICS)
GRAPH THEORY
GRAPHIC METHODS
IMAGE ANALYSIS
NETWORK SECURITY
SURVEYING
TRIANGULATION
CONTINUOUS DISK COVER
DELAU-NAY TRIANGULATIONS
GEOMETRIC PROBLEMS
HITTING SETS
SECURITY APPLICATION
STRAIGHT-LINE DRAWINGS
STRAIGHT-LINE SEGMENTS
UNIFORMLY BOUNDED
APPROXIMATION ALGORITHMS
URI: http://hdl.handle.net/10995/102043
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85039436237
PURE ID: 6254840
ff473cd7-21ca-4472-980e-cfb699c2ed39
ISSN: 3029743
ISBN: 9783319730127
DOI: 10.1007/978-3-319-73013-4_33
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85039436237.pdf195,97 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.