Improved approximation algorithms for minimum-weight vertex separators

By Uriel Feige, M. Hajiaghayi, James R. Lee. Symposium on the Theory of Computing, 2005

377 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Parameterized Complexity and Approximation Algorithms (2008, background): “([48]) Given a graph with tree width k, a tree decomposition of width at most O(k √ log k) can be constructed in polynomial time.”
GraphX: Graph Processing in a Distributed Dataflow Framework (2014, background): “This may appear to be a small accomplishment, but the tight integration of vertices and edges in specialized graph processing systems often hinders even this basic form of reuse.”
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into 1 (Extended Abstract) (2005, background): “imation to MINIMUM UNCUT and related problems [1], to VERTEX SEPARATOR [ 13 ], and to obtain a 2 − O( 1 √log n )”
Expander flows, geometric embeddings and graph partitioning (2009, positive): “Using this they v design new log n-approximation algorithms for graph deletion problems such as 2CNF-DELETION and MIN-UNCUT [Agarwal et al. 2005], for MIN-LINEAR ARRANGEMENT [Charikar et al. 2006; Feige and Lee 2007], and VERTEX SEPARATORS [Feige et al. 2005].”
Combinatorial Optimization on Graphs of Bounded Treewidth (2008, background): “[56]: one can find in polynomial time for graphs of treewidth k a tree decomposition of width O(k p log k).”