Finding small balanced separators

DOI10.1145/1132516.1132573zbMath1301.68159MaRDI 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 dimension; fixed-parameter tractability

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

68W20: Randomized algorithms

Related Items

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