Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with graph partitioning:
TR06-116 | 19th July 2006
Amin Coja-Oghlan

Graph partitioning via adaptive spectral techniques

We study the use of spectral techniques for graph partitioning. Let G=(V,E) be a graph whose vertex set has a ``latent'' partition V_1,...,V_k. Moreover, consider a ``density matrix'' E=(E_vw)_{v,w in V} such that for v in V_i and w in V_j the entry E_{vw} is the fraction of all possible ... more >>>

TR12-111 | 5th September 2012
Venkatesan Guruswami, Ali Kemal Sinop

Faster SDP hierarchy solvers for local rounding algorithms

Convex relaxations based on different hierarchies of
linear/semi-definite programs have been used recently to devise
approximation algorithms for various optimization problems. The
approximation guarantee of these algorithms improves with the number
of {\em rounds} $r$ in the hierarchy, though the complexity of solving
(or even writing down the solution for) ... more >>>

TR18-185 | 6th November 2018
Yonatan Nakar, Dana Ron

On the Testability of Graph Partition Properties

In this work we study the testability of a family of graph partition properties that generalizes a family previously studied by Goldreich, Goldwasser, and Ron (Journal of the ACM, 1998). While the family studied by Goldreich et al. includes a variety of natural properties, such as k-colorability and containing a ... more >>>

ISSN 1433-8092 | Imprint