Improved approximation algorithms for minimum-weight vertex separators

DOI10.1145/1060590.1060674zbMath1192.68893OpenAlexW2049609719WikidataQ29038299 ScholiaQ29038299MaRDI QIDQ3581405

James R. Lee, Uriel Feige, Mohammad Taghi Hajiaghayi

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060674

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

A note on multiflows and treewidth, Approximation algorithms for treewidth, \(\ell ^2_2\) spreading metrics for vertex ordering problems, Space-efficient vertex separators for treewidth, The vertex attack tolerance of complex networks, General variable neighborhood search for computing graph separators, Approximate search strategies for weighted trees, On treewidth, separators and Yao's garbling, Subexponential parameterized algorithms, Distributed chasing of network intruders, Advances in metric embedding theory, Linearity of grid minors in treewidth with applications through bidimensionality, Fréchet embeddings of negative type metrics, A hybrid breakout local search and reinforcement learning approach to the vertex separator problem, On the complexity of computing treelength, Solution methods for the vertex variant of the network system vulnerability analysis problem, On tree width, bramble size, and expansion, Approximating small balanced vertex separators in almost linear time, Nondeterministic graph searching: from pathwidth to treewidth, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth