Výsledky vyhledávání

Report

A Parameterized Approximation Scheme for Min $k$-Cut

Autor: Lokshtanov, Daniel, Saurabh, Saket, Surianarayanan, Vaishali

In the Min $k$-Cut problem, input is an edge weighted graph $G$ and an integer $k$, and the task is to partition the vertex set into $k$ non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When $k$

Externí odkaz: http://arxiv.org/abs/2005.00134

Zobrazit plný text záznamu

Conference

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Breaking the All Subsets Barrier for Min k-Cut

Autor: Lokshtanov, Daniel, Saurabh, Saket, Surianarayanan, Vaishali

In the Min k-Cut problem, the input is a graph G and an integer k. The task is to find a partition of the vertex set of G into k parts, while minimizing the number of edges that go between different parts of the partition. The problem is NP-complete,

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::e9f50714c2163a3d48d9074604ecdc9a

Zobrazit plný text záznamu

Akademický článek

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

A Parameterized Approximation Scheme for Min $k$-Cut

Autor: Saket Saurabh, Vaishali Surianarayanan, Daniel Lokshtanov

Publikováno v: FOCS
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
61st IEEE Annual Symposium on Foundations of Computer Science, FOCS

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8d7d2f5b42cafc607b70074c68a9f57d
https://doi.org/10.1137/20m1383197

Zobrazit plný text záznamu

Min-k-Cut Coalition Structure Generation on Trust-Utility Relationship Graph

Autor: Xiangrong Tong, Yingjie Wang, Xianglong Kong

Publikováno v: Wireless Communications and Mobile Computing, Vol 2021 (2021)

Trust relationships have an important effect on coalition formation. In many real scenarios, agents usually cooperate with others in their trusted social networks to form coalitions. Therefore, the trust value between agents should constrain the util

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ec2ddc63c74be98b3bea02b4b6203951
https://doaj.org/article/ea0b663f7c5d43dfb7dde23c51fe6373

Zobrazit plný text záznamu