Finding small balanced separators
From MaRDI portal
Publication:2931401
DOI10.1145/1132516.1132573zbMath1301.68159MaRDI QIDQ2931401
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
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, The Valve Location Problem in Simple Network Topologies, 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, How to Cut a Graph into Many Pieces, Algorithms for Multiterminal Cuts
