1 Search Results for "Teutrine, Eva-Lotta"

Document
DOI: 10.4230/LIPIcs.IPEC.2016.24
Improved Bounds for Minimal Feedback Vertex Sets in Tournaments

Authors: Matthias Mnich and Eva-Lotta Teutrine

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949^n minimal FVS. This significantly improves the previously best upper bound of 1.6667^n by Fomin et al. (STOC 2016). Our new upper bound almost matches the best known lower bound of 21^{n/7} approx 1.5448^n, due to Gaspers and Mnich (ESA 2010). Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time O(1.5949^n).
Cite as

Matthias Mnich and Eva-Lotta Teutrine. Improved Bounds for Minimal Feedback Vertex Sets in Tournaments. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 24:1-24:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mnich_et_al:LIPIcs.IPEC.2016.24,
  author =	{Mnich, Matthias and Teutrine, Eva-Lotta},
  title =	{{Improved Bounds for Minimal Feedback Vertex Sets in Tournaments}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{24:1--24:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.24},
  URN =		{urn:nbn:de:0030-drops-69236},
  doi =		{10.4230/LIPIcs.IPEC.2016.24},
  annote =	{Keywords: exponential-time algorithms, feedback vertex sets, tournaments}
}
  • Refine by Author
  • 1 Mnich, Matthias
  • 1 Teutrine, Eva-Lotta

  • Refine by Classification

  • Refine by Keyword
  • 1 exponential-time algorithms
  • 1 feedback vertex sets
  • 1 tournaments

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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