Zobrazeno 1 - 10
of 169
pro vyhledávání: '"Minimum k-cut"'
Publikováno v:
SIAM Journal on Discrete Mathematics. 34:1334-1353
Karger used spanning tree packings [D. R. Karger, J. ACM, 47 (2000), pp. 46--76] to derive a near linear-time randomized algorithm for the global minimum cut problem as well as a bound on the numbe...
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3c5f4fb319d8d3e748bcf99a683ad1f5
https://doi.org/10.1137/19m1299359
https://doi.org/10.1137/19m1299359
Autor:
Pasin Manurangsi
Publikováno v:
Algorithms, Vol 11, Iss 1, p 10 (2018)
The Small Set Expansion Hypothesis is a conjecture which roughly states that it is NP-hard to distinguish between a graph with a small subset of vertices whose (edge) expansion is almost zero and one in which all small subsets of vertices have expans
Externí odkaz:
https://doaj.org/article/f6c9bd85f04e4b5f8b4eb70f332de106
Publikováno v:
Journal of Parallel and Distributed Computing. 109:1-14
A cut tree is a combinatorial structure that represents the edge-connectivity between all pairs of vertices of an undirected graph. Cut trees solve the all pairs minimum s – t -cut problem efficiently. Cut trees have a large number of applications
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::17723f76dfdf8f9a8fd763e1c3fc828d
https://doi.org/10.1016/j.jpdc.2017.04.007
https://doi.org/10.1016/j.jpdc.2017.04.007
Autor:
Yotaro Takazawa, Shinji Mizuno
Publikováno v:
Journal of the Operations Research Society of Japan. 60(No. 1):15-23
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0b2e83cd3a5d1eefac67f23153ee3a69
http://t2r2.star.titech.ac.jp/cgi-bin/publicationinfo.cgi?q_publication_content_number=CTT100747444
http://t2r2.star.titech.ac.jp/cgi-bin/publicationinfo.cgi?q_publication_content_number=CTT100747444
Autor:
Jason Li
Publikováno v:
FOCS
We consider the (exact, minimum) $k$-cut problem: given a graph and an integer $k$, delete a minimum-weight set of edges so that the remaining graph has at least $k$ connected components. This problem is a natural generalization of the global minimum
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::41d177ca3f714722e7b888341b3b833c
https://doi.org/10.1109/focs.2019.00068
https://doi.org/10.1109/focs.2019.00068
Publikováno v:
STOC
Given an edge-weighted graph, how many minimum k-cuts can it have? This is a fundamental question in the intersection of algorithms, extremal combinatorics, and graph theory. It is particularly interesting in that the best known bounds are algorithmi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::61e340b11f77c0907c8a261c68ca03c2
https://doi.org/10.1145/3313276.3316395
https://doi.org/10.1145/3313276.3316395
Autor:
Pasin Manurangsi
Publikováno v:
Algorithms, Vol 11, Iss 1, p 10 (2018)
Algorithms; Volume 11; Issue 1; Pages: 10
Algorithms; Volume 11; Issue 1; Pages: 10
The Small Set Expansion Hypothesis (SSEH) is a conjecture which roughly states that it is NP-hard to distinguish between a graph with a small subset of vertices whose edge expansion is almost zero and one in which all small subsets of vertices have e
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f0ddd2a6ae2542e5dbee73590d3fc543
Publikováno v:
Electronic Notes in Discrete Mathematics. 55:135-138
We consider a constraint minimum cost flow problem and show that it is in general NP –complete. For special graph classes we give (pseudo–)polynomial algorithms.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::fa0041f23ec88b84a9b551c6b4c98f4b
https://doi.org/10.1016/j.endm.2016.10.034
https://doi.org/10.1016/j.endm.2016.10.034
Autor:
Franklin H. J. Kenter
Publikováno v:
Operations Research Letters. 44:255-259
The minimum rank problem asks to find the minimum rank over all matrices with a given pattern associated with a graph. This problem is NP-hard, and there is no known approximation method. Further, this problem has no straightforward convex relaxation
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ba8ceae400e327be0cbe758600b50c0b
https://doi.org/10.1016/j.orl.2016.02.001
https://doi.org/10.1016/j.orl.2016.02.001
Publikováno v:
Theoretical Computer Science. 609:434-442
In some application cases, the solutions of combinatorial optimization problems on graphs should satisfy an additional vertex size constraint. In this paper, we consider size-constrained minimum s-t cut problems and size-constrained dense subgraph pr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ab3ca5d3ec4ce2bcd429075119a6802e
https://doi.org/10.1016/j.tcs.2015.10.031
https://doi.org/10.1016/j.tcs.2015.10.031