Vertex connectivity augmentation is FPT parameterized by λ and k with running time 2^{O(k log(k+λ))} n^{O(1)}; edge connectivity augmentation is FPT parameterized by k alone.
Fixed-parameter tractability of multicut parameterized by the size of the cutset.SIAM J
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2verdicts
UNVERDICTED 2representative citing papers
Connectivity-preserving important separators of size at most k number 2^{O(k log k)} and can be enumerated in the same bound, yielding 2^{O(k log k)} FPT time for constant-class Node Multiway Cut-Uncut.
citing papers explorer
-
Connectivity augmentation is fixed-parameter tractable
Vertex connectivity augmentation is FPT parameterized by λ and k with running time 2^{O(k log(k+λ))} n^{O(1)}; edge connectivity augmentation is FPT parameterized by k alone.
-
Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
Connectivity-preserving important separators of size at most k number 2^{O(k log k)} and can be enumerated in the same bound, yielding 2^{O(k log k)} FPT time for constant-class Node Multiway Cut-Uncut.