Representative Sets and Irrelevant Vertices
From MaRDI portal
Publication:5133971
DOI10.1145/3390887zbMath1491.68092arXiv1111.2195OpenAlexW3039254663MaRDI QIDQ5133971
Stefan Kratsch, Magnus Wahlström
Publication date: 11 November 2020
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1111.2195
Analysis of algorithms (68W40) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (27)
On polynomial kernels for sparse integer linear programs ⋮ Deterministic Truncation of Linear Matroids ⋮ On kernelization and approximation for the vector connectivity problem ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ Parameterized complexity of weighted multicut in trees ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Multicut Is FPT ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. ⋮ Multi-Budgeted Directed Cuts ⋮ A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ On the approximate compressibility of connected vertex cover ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation) ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Unnamed Item ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ An exponential lower bound for cut sparsifiers in planar graphs ⋮ Smaller Parameters for Vertex Cover Kernelization ⋮ Path-Contractions, Edge Deletions and Connectivity Preservation ⋮ On group feedback vertex set parameterized by the size of the cutset
This page was built for publication: Representative Sets and Irrelevant Vertices
