Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems

We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph G = ( V , E ) with edge-weights w : E → R ≥ 0 and vertex-weights η : V → R + are given. The goal is to find a vertex set S ⊆ V...

Full description

Bibliographic Details
Published in:Journal of computer and system sciences : JCSS, Vol. 82, No. 6 (2016), p. 1044-1063
Main Author: Hasan, Mohammad Khairul (Author)
Other Involved Persons: Chwa, Kyung-Yong
Format: electronic Article
Language:English
ISSN:1090-2724
Physical Description:Online-Ressource
DOI:10.1016/j.jcss.2016.03.004
QR Code: Show QR Code