CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Pareto complexity of two-parameter FPT problems: A case study for partial vertex cover

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
4th International Workshop on Parameterized and Exact Computation IWPEC 2009, Lecture Notes in Computer Science Vol. 5917 (2009), p. 110-121.
[Konferensbidrag, refereegranskat]

We propose a framework for the complexity of algorithms for FPT problems with two separate parameters k,m and with exponential time bounds O(x^ky^m)where x,y>1 are constant bases. An optimal combination of bases x,y can be chosen depending on the ratio m/k. As a first illustration we apply the framework to the problem of finding, in a graph, a vertex cover of size k that leaves at most m edges uncovered. We report the best branching rules we could find so far, for all ranges of ratio m/k.

Nyckelord: parameterized algorithm, multiple parameters, Pareto curve, partial vertex cover



Denna post skapades 2010-01-12. Senast ändrad 2015-02-11.
CPL Pubid: 106565