Finding small balanced separators
From MaRDI portal
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Recommendations
- Approximating small balanced vertex separators in almost linear time
- Approximating small balanced vertex separators in almost linear time
- A Heuristic Algorithm for Small Separators in Arbitrary Graphs
- Finding good approximate vertex and edge partitions is NP-hard
- Fast Approximate Graph Partitioning Algorithms
Cited in
(26)- Faster exponential-time approximation algorithms using approximate monotone local search
- Most balanced minimum cuts
- Algorithms for Multiterminal Cuts
- Partitioning a graph into small pieces with applications to path transversal
- The Valve Location Problem in Simple Network Topologies
- Finding good approximate vertex and edge partitions is NP-hard
- Hardness of finding combinatorial shortest paths on graph associahedra
- A Heuristic Algorithm for Small Separators in Arbitrary Graphs
- On classes of graphs with strongly sublinear separators
- A hybrid breakout local search and reinforcement learning approach to the vertex separator problem
- Customizable hub labeling: properties and algorithms
- On treewidth, separators and Yao's garbling
- Linear kernels for separating a graph into components of bounded size
- Simple and improved parameterized algorithms for multiterminal cuts
- Solution methods for the vertex variant of the network system vulnerability analysis problem
- Operational causality -- necessarily sufficient and sufficiently necessary
- Approximating small balanced vertex separators in almost linear time
- Approximating small balanced vertex separators in almost linear time
- Cuts in graphs with matroid constraints
- How to Cut a Graph into Many Pieces
- On the parameterized complexity of finding separators with non-hereditary properties
- scientific article; zbMATH DE number 7626718 (Why is no real title available?)
- Brief announcement: Bounded-degree cut is fixed-parameter tractable
- Detecting a Network Failure
- Fission: Practical algorithms for computing minimum balanced node separators
- Minimum Bisection Is Fixed-Parameter Tractable
This page was built for publication: Finding small balanced separators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931401)
