Hitting set problem for axis-parallel squares intersecting a straight line is polynomially solvable for any fixed range of square sizes

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

Original languageEnglish
Title of host publicationAnalysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
PublisherSpringer Verlag
Pages334-345
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

Hitting Set
Straight Line
Range of data
Unit
Heat Shock Protein
Algorithm Complexity
Discrete Optimization
Computational Geometry
Operations Research
Time-average
Optimal Algorithm
Hits
Graph theory
Rectangle
Polynomial-time Algorithm
Computational geometry
Machine Learning
Operations research
NP-complete problem
Optimization Problem

Keywords

  • Computational geometry
  • Dynamic programming
  • Hitting set problem
  • Parameterized complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

WoS ResearchAreas Categories

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

Cite this

Khachay, D., Khachay, M., & Poberiy, M. (2018). Hitting set problem for axis-parallel squares intersecting a straight line is polynomially solvable for any fixed range of square sizes. In Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers (Vol. 10716 LNCS, pp. 334-345). (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_31
Khachay, Daniel ; Khachay, Michael ; Poberiy, Maria. / Hitting set problem for axis-parallel squares intersecting a straight line is polynomially solvable for any fixed range of square sizes. Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Vol. 10716 LNCS Springer Verlag, 2018. pp. 334-345 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{4fd1d97daf9349f3b6d10fbde3898675,
title = "Hitting set problem for axis-parallel squares intersecting a straight line is polynomially solvable for any fixed range of square sizes",
keywords = "Computational geometry, Dynamic programming, Hitting set problem, Parameterized complexity",
author = "Daniel Khachay and Michael Khachay and Maria Poberiy",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-319-73013-4_31",
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 = "334--345",
booktitle = "Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers",
address = "Germany",

}

Khachay, D, Khachay, M & Poberiy, M 2018, Hitting set problem for axis-parallel squares intersecting a straight line is polynomially solvable for any fixed range of square sizes. 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. 334-345, 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_31

Hitting set problem for axis-parallel squares intersecting a straight line is polynomially solvable for any fixed range of square sizes. / Khachay, Daniel; Khachay, Michael; Poberiy, Maria.

Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Vol. 10716 LNCS Springer Verlag, 2018. p. 334-345 (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 - Hitting set problem for axis-parallel squares intersecting a straight line is polynomially solvable for any fixed range of square sizes

AU - Khachay, Daniel

AU - Khachay, Michael

AU - Poberiy, Maria

PY - 2018/1/1

Y1 - 2018/1/1

KW - Computational geometry

KW - Dynamic programming

KW - Hitting set problem

KW - Parameterized complexity

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

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

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

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

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 - 334

EP - 345

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

PB - Springer Verlag

ER -

Khachay D, Khachay M, Poberiy M. Hitting set problem for axis-parallel squares intersecting a straight line is polynomially solvable for any fixed range of square sizes. In Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Vol. 10716 LNCS. Springer Verlag. 2018. p. 334-345. (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_31