An FPT Algorithm for the Correlation Clustering Problem

Abstract:

Article Preview

Given an undirected graph G=(V, E) with real nonnegative weights and + or – labels on its edges, the correlation clustering problem is to partition the vertices of G into clusters to minimize the total weight of cut + edges and uncut – edges. This problem is APX-hard and has been intensively studied mainly from the viewpoint of polynomial time approximation algorithms. By way of contrast, a fixed-parameter tractable algorithm is presented that takes treewidth as the parameter, with a running time that is linear in the number of vertices of G.

Info:

Periodical:

Key Engineering Materials (Volumes 474-476)

Edited by:

Garry Zhu

Pages:

924-927

DOI:

10.4028/www.scientific.net/KEM.474-476.924

Citation:

X. Xin "An FPT Algorithm for the Correlation Clustering Problem", Key Engineering Materials, Vols. 474-476, pp. 924-927, 2011

Online since:

April 2011

Authors:

Export:

Price:

$35.00

In order to see related information, you need to Login.

In order to see related information, you need to Login.