Finding small balanced separators

DOI10.1145/1132516.1132573zbMath1301.68159OpenAlexW2106515361MaRDI QIDQ2931401

Mohammad Mahdian, Uriel Feige

Publication date: 25 November 2014

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

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

zbMATH Keywords

VC dimensionfixed-parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Linear kernels for separating a graph into components of bounded size ⋮ Algorithms for Multiterminal Cuts ⋮ Customizable hub labeling: properties and algorithms ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ Operational causality -- necessarily sufficient and sufficiently necessary ⋮ Unnamed Item ⋮ On treewidth, separators and Yao's garbling ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ How to Cut a Graph into Many Pieces ⋮ Unnamed Item ⋮ On classes of graphs with strongly sublinear separators ⋮ A hybrid breakout local search and reinforcement learning approach to the vertex separator problem ⋮ Most balanced minimum cuts ⋮ Solution methods for the vertex variant of the network system vulnerability analysis problem ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ Approximating small balanced vertex separators in almost linear time ⋮ The Valve Location Problem in Simple Network Topologies