• Parameterized complexity of ca...

Treffer: Parameterized complexity of cardinality constrained optimization problems

Title:
Parameterized complexity of cardinality constrained optimization problems
Authors:
Leizhen Cai
Contributors:
The Pennsylvania State University CiteSeerX Archives
Source:
http://comjnl.oxfordjournals.org/cgi/reprint/bxm086v1.pdf.
Publication Year:
2006
Collection:
CiteSeerX
Subject Terms:
cardinality constrained optimization problem, exact algorithm, fixed-cardinality optimization problem, graph problem, parameterized complexity, FPT algorithm
Document Type:
Fachzeitschrift text
File Description:
application/pdf
Language:
English
Relation:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.7121; http://comjnl.oxfordjournals.org/cgi/reprint/bxm086v1.pdf
Availability:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.7121
http://comjnl.oxfordjournals.org/cgi/reprint/bxm086v1.pdf
Rights:
Metadata may be used without restrictions as long as the oai identifier remains attached to it.
Accession Number:
edsbas.BACAE8E2
Database:
BASE

Weitere Informationen

We study the parameterized complexity of cardinality constrained optimization problems, i.e. optimization problems that require their solutions to contain specified numbers of elements to optimize solution values. For this purpose, we consider around 20 such optimization problems, as well as their parametric duals, that deal with various fundamental relations among vertices and edges in graphs. We have almost completely settled their parameterized complexity by giving either FPT algorithms or W[1]-hardness proofs. Furthermore, we obtain faster exact algorithms for several cardinality constrained optimization problems by transforming them into problems of finding maximum (minimum) weight triangles in weighted graphs.