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




Related Items (27)

On polynomial kernels for sparse integer linear programsDeterministic Truncation of Linear MatroidsOn kernelization and approximation for the vector connectivity problemPreprocessing to reduce the search space: antler structures for feedback vertex setSolving min ones 2-SAT as fast as vertex coverElimination Distances, Blocking Sets, and Kernels for Vertex CoverParameterized complexity of weighted multicut in treesHitting Minors on Bounded Treewidth Graphs. IV. An Optimal AlgorithmAn ETH-tight algorithm for bidirected Steiner connectivityOn Weighted Graph Separation Problems and Flow AugmentationMulticut Is FPTA randomized polynomial kernel for subset feedback vertex setPolynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.Multi-Budgeted Directed CutsA Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar GraphsParameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphsOn the approximate compressibility of connected vertex coverTree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)An improved FPT algorithm for independent feedback vertex setComputing subset transversals in \(H\)-free graphsUnnamed ItemHalf-integrality, LP-branching, and FPT AlgorithmsPolynomial kernels for vertex cover parameterized by small degree modulatorsAn exponential lower bound for cut sparsifiers in planar graphsSmaller Parameters for Vertex Cover KernelizationPath-Contractions, Edge Deletions and Connectivity PreservationOn group feedback vertex set parameterized by the size of the cutset




This page was built for publication: Representative Sets and Irrelevant Vertices