Compression via Matroids
From MaRDI portal
Publication:4962154
DOI10.1145/2635810zbMath1398.68250arXiv1107.3068OpenAlexW2119741712MaRDI QIDQ4962154
Stefan Kratsch, Magnus Wahlström
Publication date: 30 October 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1107.3068
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (25)
Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Proximity Search for Maximal Subgraph Enumeration ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion} ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ An Updated Experimental Evaluation of Graph Bipartization Methods ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Unnamed Item ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Edge bipartization faster than \(2^k\) ⋮ Multi-Budgeted Directed Cuts ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ 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 ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation) ⋮ Linear representation of transversal matroids and gammoids parameterized by rank ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs ⋮ Multi-budgeted directed cuts
This page was built for publication: Compression via Matroids
