Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
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.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Revised Papers |
| Редакторы | Ignasi Sau, Dimitrios M. Thilikos |
| Издатель | Springer Nature |
| Страницы | 148-161 |
| Число страниц | 14 |
| ISBN (печатное издание) | 9783030307851 |
| DOI | |
| Состояние | Опубликовано - 1 янв 2019 |
| Событие | 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 - Catalonia, Испания Продолжительность: 19 июн 2019 → 21 июн 2019 |
| Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Том | 11789 LNCS |
| ISSN (печатное издание) | 0302-9743 |
| ISSN (электронное издание) | 1611-3349 |
| конференция | 45th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2019 |
|---|---|
| Страна/Tерритория | Испания |
| Город | Catalonia |
| Период | 19/06/19 → 21/06/19 |
ID: 49787206