TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publications
  4. Improved bounds for minimal feedback vertex sets in tournaments
 
Options

Improved bounds for minimal feedback vertex sets in tournaments

Citation Link: https://doi.org/10.15480/882.2634
Publikationstyp
Journal Article
Date Issued
2017-12-08
Sprache
English
Author(s)
Mnich, Matthias  orcid-logo
Teutrine, Eva Lotta  
TORE-DOI
10.15480/882.2634
TORE-URI
http://hdl.handle.net/11420/4534
Journal
Journal of graph theory  
Volume
88
Issue
3
Start Page
482
End Page
506
Citation
Journal of Graph Theory (2018)
Publisher DOI
10.1002/jgt.22225
Publisher
Wiley-Blackwell
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.5949n minimal FVS. This significantly improves the previously best upper bound of 1.6667^n by Fomin et al. [STOC 2016] and 1.6740^n by Gaspers and Mnich [J. Graph Theory 72(1):72–89, 2013]. Our new upper bound almost matches the best-known lower bound of 21^n/7≈1.5448^n, due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time O(1.5949^n).
Subjects
combinatorial bounds
exponential-time algorithms
feedback vertex sets
tournaments
DDC Class
004: Informatik
Lizenz
https://creativecommons.org/licenses/by/4.0/
Loading...
Thumbnail Image
Name

Mnich_et_al-2018-Journal_of_Graph_Theory.pdf

Size

1.95 MB

Format

Adobe PDF

TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback