1 Search Results for "An, Shinwoo"

Document
DOI: 10.4230/LIPIcs.ISAAC.2021.47
Feedback Vertex Set on Geometric Intersection Graphs

Authors: Shinwoo An and Eunjin Oh

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
In this paper, we present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time 2^O(√k)(n+m), where n and m denote the numbers of vertices and edges, respectively. This improves the 2^O(√klog k) n^O(1)-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017]. Moreover, our algorithm is optimal assuming the exponential-time hypothesis. Also, our algorithm can be extended to handle geometric intersection graphs of similarly sized fat objects without increasing the running time.
Cite as

Shinwoo An and Eunjin Oh. Feedback Vertex Set on Geometric Intersection Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 47:1-47:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.ISAAC.2021.47,
  author =	{An, Shinwoo and Oh, Eunjin},
  title =	{{Feedback Vertex Set on Geometric Intersection Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{47:1--47:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.47},
  URN =		{urn:nbn:de:0030-drops-154807},
  doi =		{10.4230/LIPIcs.ISAAC.2021.47},
  annote =	{Keywords: Feedback vertex set, intersection graphs, parameterized algorithm}
}
  • Refine by Author
  • 1 An, Shinwoo
  • 1 Oh, Eunjin

  • Refine by Classification
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Feedback vertex set
  • 1 intersection graphs
  • 1 parameterized algorithm

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact