Kociumaka, Tomasz and Pilipczuk, Marcin (2014) Faster deterministic feedback vertex set. Information Processing Letters, Volume 114 (Number 10). pp. 556-560. doi:10.1016/j.ipl.2014.05.001 ISSN 0020-0190.

Preview

PDF WRAP_1371795-cs-270115-fvs-golden.pdf - Accepted Version - Requires a PDF viewer. Download (389Kb) | Preview

Request Changes to record.

Abstract

We present a new deterministic algorithm for the Feedback Vertex Set problem parameterized by the solution size. Our algorithm runs in O*((2+ϕ)k) time, where ϕ<1.619 is the golden ratio, surpassing the previously fastest O*((1 + 2√2)k)-time deterministic algorithm due to Cao et al. (2010) [6]. In our development we follow the approach of Cao et al.; however, thanks to a new reduction rule, we obtain not only better dependency on the parameter in the running time, but also a solution with simple analysis and only a single branching rule.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH):	Graph theory
Journal or Publication Title:	Information Processing Letters
Publisher:	Elsevier Science BV
ISSN:	0020-0190
Official Date:	October 2014
Dates:	Date Event October 2014 Published 9 May 2014 Available 1 May 2013 Accepted 11 September 2013 Submitted
Volume:	Volume 114
Number:	Number 10
Page Range:	pp. 556-560
DOI:	10.1016/j.ipl.2014.05.001
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	28 December 2015
Date of first compliant Open Access:	28 December 2015
Funder:	Narodowe Centrum Nauki (NCN), Fundacja na rzecz Nauki Polskiej [Foundation for Polish Science] (FNP)
Grant number:	UMO-2012/05/D/ST6/03214 (NCN)
Embodied As:	1

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads