Stabbing line segments with disks: Complexity and approximation algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

1 Citation (Scopus)
Original languageEnglish
Title of host publicationAnalysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
PublisherSpringer Verlag
Pages356-367
Number of pages12
Volume10716 LNCS
ISBN (Print)9783319730127
DOIs
Publication statusPublished - 1 Jan 2018
Event6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 - Moscow, Russian Federation
Duration: 27 Jul 201729 Jul 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10716 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
CountryRussian Federation
CityMoscow
Period27/07/201729/07/2017

Fingerprint

Approximation algorithms
Line segment
Approximation Algorithms
Straight Line
Line Drawing
Network security
Triangulation
Planar graph
Computational complexity
Hardness
NP-hardness
Delaunay triangulation
Network Security
Network Design
Graph in graph theory
Linear Function
Subgraph
Cardinality
Euclidean
Computational Complexity

Keywords

  • Approximation algorithms
  • Computational complexity
  • Continuous disk cover
  • Delaunay triangulations
  • Hitting set

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

WoS ResearchAreas Categories

  • Computer Science, Information Systems
  • Computer Science, Theory & Methods

Cite this

Kobylkin, K. (2018). Stabbing line segments with disks: Complexity and approximation algorithms. In Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers (Vol. 10716 LNCS, pp. 356-367). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10716 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-73013-4_33
Kobylkin, Konstantin. / Stabbing line segments with disks: Complexity and approximation algorithms. Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Vol. 10716 LNCS Springer Verlag, 2018. pp. 356-367 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{ff473cd721ca4472980ecfb699c2ed39,
title = "Stabbing line segments with disks: Complexity and approximation algorithms",
keywords = "Approximation algorithms, Computational complexity, Continuous disk cover, Delaunay triangulations, Hitting set",
author = "Konstantin Kobylkin",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-319-73013-4_33",
language = "English",
isbn = "9783319730127",
volume = "10716 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "356--367",
booktitle = "Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers",
address = "Germany",

}

Kobylkin, K 2018, Stabbing line segments with disks: Complexity and approximation algorithms. in Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. vol. 10716 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10716 LNCS, Springer Verlag, pp. 356-367, 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017, Moscow, Russian Federation, 27/07/2017. https://doi.org/10.1007/978-3-319-73013-4_33

Stabbing line segments with disks: Complexity and approximation algorithms. / Kobylkin, Konstantin.

Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Vol. 10716 LNCS Springer Verlag, 2018. p. 356-367 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10716 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - Stabbing line segments with disks: Complexity and approximation algorithms

AU - Kobylkin, Konstantin

PY - 2018/1/1

Y1 - 2018/1/1

KW - Approximation algorithms

KW - Computational complexity

KW - Continuous disk cover

KW - Delaunay triangulations

KW - Hitting set

UR - http://www.scopus.com/inward/record.url?scp=85039436237&partnerID=8YFLogxK

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000441461800033

U2 - 10.1007/978-3-319-73013-4_33

DO - 10.1007/978-3-319-73013-4_33

M3 - Conference contribution

SN - 9783319730127

VL - 10716 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 356

EP - 367

BT - Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers

PB - Springer Verlag

ER -

Kobylkin K. Stabbing line segments with disks: Complexity and approximation algorithms. In Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Vol. 10716 LNCS. Springer Verlag. 2018. p. 356-367. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-73013-4_33