On the parameterized complexity of labelled correlation clustering problem

Xianmin Liu; Jianzhong Li; Hong Gao

doi:10.1007/978-3-319-08783-2_24

On the parameterized complexity of labelled correlation clustering problem

Xianmin Liu
, Jianzhong Li^*
, Hong Gao

^*Corresponding author for this work

Faculty of Computing

Harbin Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The Labelled Correlation Clustering problem, a variant of Correlation Clustering problem, is defined and studied in this paper. Since the problem is NP-complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied.

Original language	English
Title of host publication	Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
Publisher	Springer Verlag
Pages	276-287
Number of pages	12
ISBN (Print)	9783319087825
DOIs	https://doi.org/10.1007/978-3-319-08783-2_24
State	Published - 2014
Event	20th International Computing and Combinatorics Conference, COCOON 2014 - Atlanta, GA, United States Duration: 4 Aug 2014 → 6 Aug 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8591 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Computing and Combinatorics Conference, COCOON 2014
Country/Territory	United States
City	Atlanta, GA
Period	4/08/14 → 6/08/14

Access to Document

10.1007/978-3-319-08783-2_24

Cite this

Liu, X., Li, J., & Gao, H. (2014). On the parameterized complexity of labelled correlation clustering problem. In Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings (pp. 276-287). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8591 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-08783-2_24

Liu, Xianmin ; Li, Jianzhong ; Gao, Hong. / On the parameterized complexity of labelled correlation clustering problem. Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings. Springer Verlag, 2014. pp. 276-287 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{eb1ee8542d704354b44e9a402ac30b5c,

title = "On the parameterized complexity of labelled correlation clustering problem",

abstract = "The Labelled Correlation Clustering problem, a variant of Correlation Clustering problem, is defined and studied in this paper. Since the problem is NP-complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied.",

author = "Xianmin Liu and Jianzhong Li and Hong Gao",

year = "2014",

doi = "10.1007/978-3-319-08783-2\_24",

language = "英语",

isbn = "9783319087825",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "276--287",

booktitle = "Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings",

address = "德国",

note = "20th International Computing and Combinatorics Conference, COCOON 2014 ; Conference date: 04-08-2014 Through 06-08-2014",

}

Liu, X, Li, J & Gao, H 2014, On the parameterized complexity of labelled correlation clustering problem. in Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8591 LNCS, Springer Verlag, pp. 276-287, 20th International Computing and Combinatorics Conference, COCOON 2014, Atlanta, GA, United States, 4/08/14. https://doi.org/10.1007/978-3-319-08783-2_24

On the parameterized complexity of labelled correlation clustering problem. / Liu, Xianmin; Li, Jianzhong; Gao, Hong.
Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings. Springer Verlag, 2014. p. 276-287 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8591 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the parameterized complexity of labelled correlation clustering problem

AU - Liu, Xianmin

AU - Li, Jianzhong

AU - Gao, Hong

PY - 2014

Y1 - 2014

N2 - The Labelled Correlation Clustering problem, a variant of Correlation Clustering problem, is defined and studied in this paper. Since the problem is NP-complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied.

AB - The Labelled Correlation Clustering problem, a variant of Correlation Clustering problem, is defined and studied in this paper. Since the problem is NP-complete, we consider the parameterized complexities. Three different parameterizations are considered, and the corresponding parameterized complexities are studied.

UR - https://www.scopus.com/pages/publications/84904733978

U2 - 10.1007/978-3-319-08783-2_24

DO - 10.1007/978-3-319-08783-2_24

M3 - 会议稿件

AN - SCOPUS:84904733978

SN - 9783319087825

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 276

EP - 287

BT - Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings

PB - Springer Verlag

T2 - 20th International Computing and Combinatorics Conference, COCOON 2014

Y2 - 4 August 2014 through 6 August 2014

ER -

Liu X, Li J, Gao H. On the parameterized complexity of labelled correlation clustering problem. In Computing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings. Springer Verlag. 2014. p. 276-287. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-08783-2_24

On the parameterized complexity of labelled correlation clustering problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this