Back to Search
Start Over
Linear kernel for Rooted Triplet Inconsistency and other problems based on conflict packing technique.
- Source :
-
Journal of Computer & System Sciences . Mar2016, Vol. 82 Issue 2, p366-379. 14p. - Publication Year :
- 2016
-
Abstract
- We develop a technique, that we call conflict packing , to obtain (and improve) polynomial kernels for several well-studied editing problems. We first illustrate our technique on Feedback Arc Set in Tournaments ( k -FAST ) yielding an alternative and simple proof of a linear kernel for this problem. The technique is then applied to obtain the first linear kernel for the Dense Rooted Triplet Inconsistency ( k -dense-RTI ) problem. A linear kernel for Betweenness in Tournaments ( k -BIT ) is also proved. All these problems share common features. First, they can be expressed as modification problems on a dense set of constant-arity constraints. Also the consistency of the set of constraints can be characterized by means of a bounded size obstructions. The conflict packing technique basically consists of computing a maximal set of small obstructions allowing us either to bound the size of the input or to reduce the input. [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYNOMIALS
*ALGORITHMS
*KERNEL functions
*PROBLEM solving
*FEATURE extraction
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 82
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 111185343
- Full Text :
- https://doi.org/10.1016/j.jcss.2015.08.002