Linear representation of transversal matroids and gammoids parameterized by rank

DOI10.1016/j.tcs.2018.02.029zbMath1433.68181OpenAlexW2728790685WikidataQ130188335 ScholiaQ130188335MaRDI QIDQ5918110

M. S. Ramanujan, Fahad Panolan, Pranabendu Misra, Saket Saurabh

Publication date: 7 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.02.029

zbMATH Keywords

fixed-parameter tractabilitytransversal matroidsmatroid representationgammoids

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial aspects of matroids and geometric lattices (05B35) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective

Cites Work

• Unnamed Item
• A parameterized view on matroid optimization problems
• Gammoids and transversal matroids
• Representative Sets of Product Families
• Representative Families: A Unified Tradeoff-Based Approach
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Deterministic Truncation of Linear Matroids
• Editing to Connected f-Degree Graph
• A Randomized Polynomial Kernel for Subset Feedback Vertex Set
• Compression via Matroids
• Finding Even Subgraphs Even Faster
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Linear representation of transversal matroids and gammoids parameterized by rank