Output details
11 - Computer Science and Informatics
Birkbeck College
Article title
Finding small separators in linear time via treewidth reduction
Type
D - Journal article
DOI
Title of journal
ACM Transactions on Algorithms
Article number
30
Volume number
9
Issue number
4
First page of article
1
ISSN of journal
15496325
Year of publication
2013
URL
-
Number of additional authors
2
Additional information
<12> We formulate and prove a deep Treewidth Reduction Theorem. An immediate consequence of this theorem is that any graph-theoretic problem fitting a certain template is fixed-parameter tractable. The strength of the proof methodology is evidenced by the fact that we have established fixed-parameter tractability of 4 seemingly unrelated open problems posed by different research groups in the last 8 years by showing that these problems fit the template. This paper is an extended version of a paper presented at STACS'10.
Interdisciplinary
-
Cross-referral requested
-
Research group
A - Computational Intelligence
Citation count
-
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
