Standard

On Happy Colorings, Cuts, and Structural Parameterizations. / Bliznets, Ivan; Sagunov, Danil.

Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers. ed. / Ignasi Sau; Dimitrios M. Thilikos. Springer Nature, 2019. p. 148-161 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11789 LNCS).

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

Harvard

Bliznets, I & Sagunov, D 2019, On Happy Colorings, Cuts, and Structural Parameterizations. in I Sau & DM Thilikos (eds), Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11789 LNCS, Springer Nature, pp. 148-161, 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019, Catalonia, Spain, 19/06/19. https://doi.org/10.1007/978-3-030-30786-8_12

APA

Bliznets, I., & Sagunov, D. (2019). On Happy Colorings, Cuts, and Structural Parameterizations. In I. Sau, & D. M. Thilikos (Eds.), Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers (pp. 148-161). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11789 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-30786-8_12

Vancouver

Bliznets I, Sagunov D. On Happy Colorings, Cuts, and Structural Parameterizations. In Sau I, Thilikos DM, editors, Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers. Springer Nature. 2019. p. 148-161. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-30786-8_12

Author

Bliznets, Ivan ; Sagunov, Danil. / On Happy Colorings, Cuts, and Structural Parameterizations. Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers. editor / Ignasi Sau ; Dimitrios M. Thilikos. Springer Nature, 2019. pp. 148-161 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{ffa3975b78ad494c9513730b1b57049f,
title = "On Happy Colorings, Cuts, and Structural Parameterizations",
abstract = "We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters. The second problem gives a natural generalization of Multiway Uncut, which is the complement of the classical Multiway Cut problem. Due to their fundamental role in theory and practice, clusterization and cut problems has always attracted a lot of attention. We establish a new connection between these two classes of problems by providing a reduction between Maximum Happy Vertices and Node Multiway Cut. Moreover, we study structural and distance to triviality parameterizations of Maximum Happy Vertices and Maximum Happy Edges. Obtained results in these directions answer questions explicitly asked in four works: Agrawal {\textquoteright}17, Aravind et al. {\textquoteright}16, Choudhari and Reddy {\textquoteright}18, Misra and Reddy {\textquoteright}17.",
keywords = "Clique-width, Distance to triviality, Happy coloring, Homophily law, Maximum happy edges, Maximum happy vertices, Multiway cut, Parameterized complexity, Treewidth",
author = "Ivan Bliznets and Danil Sagunov",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-30786-8_12",
language = "English",
isbn = "9783030307851",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "148--161",
editor = "Ignasi Sau and Thilikos, {Dimitrios M.}",
booktitle = "Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers",
address = "Germany",
note = "45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 ; Conference date: 19-06-2019 Through 21-06-2019",

}

RIS

TY - GEN

T1 - On Happy Colorings, Cuts, and Structural Parameterizations

AU - Bliznets, Ivan

AU - Sagunov, Danil

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters. The second problem gives a natural generalization of Multiway Uncut, which is the complement of the classical Multiway Cut problem. Due to their fundamental role in theory and practice, clusterization and cut problems has always attracted a lot of attention. We establish a new connection between these two classes of problems by providing a reduction between Maximum Happy Vertices and Node Multiway Cut. Moreover, we study structural and distance to triviality parameterizations of Maximum Happy Vertices and Maximum Happy Edges. Obtained results in these directions answer questions explicitly asked in four works: Agrawal ’17, Aravind et al. ’16, Choudhari and Reddy ’18, Misra and Reddy ’17.

AB - We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters. The second problem gives a natural generalization of Multiway Uncut, which is the complement of the classical Multiway Cut problem. Due to their fundamental role in theory and practice, clusterization and cut problems has always attracted a lot of attention. We establish a new connection between these two classes of problems by providing a reduction between Maximum Happy Vertices and Node Multiway Cut. Moreover, we study structural and distance to triviality parameterizations of Maximum Happy Vertices and Maximum Happy Edges. Obtained results in these directions answer questions explicitly asked in four works: Agrawal ’17, Aravind et al. ’16, Choudhari and Reddy ’18, Misra and Reddy ’17.

KW - Clique-width

KW - Distance to triviality

KW - Happy coloring

KW - Homophily law

KW - Maximum happy edges

KW - Maximum happy vertices

KW - Multiway cut

KW - Parameterized complexity

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85072874230&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/happy-colorings-cuts-structural-parameterizations

U2 - 10.1007/978-3-030-30786-8_12

DO - 10.1007/978-3-030-30786-8_12

M3 - Conference contribution

AN - SCOPUS:85072874230

SN - 9783030307851

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

SP - 148

EP - 161

BT - Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers

A2 - Sau, Ignasi

A2 - Thilikos, Dimitrios M.

PB - Springer Nature

T2 - 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019

Y2 - 19 June 2019 through 21 June 2019

ER -

ID: 49787206