Finding small separators in linear time via treewidth reduction
From MaRDI portal
Publication:2933661
DOI10.1145/2500119zbMath1301.05337arXiv1110.4765OpenAlexW1981591809MaRDI QIDQ2933661
Dániel Marx, Igor Razgon, Barry O'Sullivan
Publication date: 5 December 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.4765
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (39)
Linear kernels for separating a graph into components of bounded size ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Chordal editing is fixed-parameter tractable ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Parameterized complexity of the \(k\)-arc Chinese postman problem ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ On kernelization and approximation for the vector connectivity problem ⋮ Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion} ⋮ Increasing the minimum degree of a graph by contractions ⋮ Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ Hitting Selected (Odd) Cycles ⋮ Some results on connected vertex separators ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Multicut Is FPT ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Multi-Budgeted Directed Cuts ⋮ Unit interval editing is fixed-parameter tractable ⋮ Parameterized complexity of critical node cuts ⋮ Contracting to a longest path in H-free graphs ⋮ Minimization and parameterized variants of vertex partition problems on graphs ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ List H-coloring a graph by removing few vertices ⋮ Rank reduction of oriented graphs by vertex and edge deletions ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ Unnamed Item ⋮ The parameterized complexity of the minimum shared edges problem ⋮ Multi-budgeted directed cuts ⋮ Euler Digraphs ⋮ Independent Feedback Vertex Set for P_5-free Graphs
This page was built for publication: Finding small separators in linear time via treewidth reduction
