Quasipolynomial representation of transversal matroids with applications in parameterized complexity
From MaRDI portal
Publication:4993296
DOI10.4230/LIPICS.ITCS.2018.32zbMATH Open1462.68081MaRDI QIDQ4993296FDOQ4993296
Authors: Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh, Meirav Zehavi 
Publication date: 15 June 2021
Recommendations
- A fast algorithm to construct a representation for transversal matroids
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Efficient computation of representative sets with applications in parameterized and exact algorithms
- Linear representation of transversal matroids and gammoids parameterized by rank
- Linear representation of transversal matroids and gammoids parameterized by rank
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Powers of tensors and fast matrix multiplication
- A probabilistic remark on algebraic program testing
- Finding and counting vertex-colored subtrees
- Constrained multilinear detection and generalized graph motifs
- Title not available (Why is that?)
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Title not available (Why is that?)
- Constrained multilinear detection for faster functional motif discovery
- Matching is as easy as matrix inversion
- Algorithms for topology-free and alignment network queries
- Deterministic parameterized algorithms for the graph motif problem
- Deterministic algorithms for matching and packing problems based on representative sets
- A parameterized view on matroid optimization problems
- Subexponential algorithms for rectilinear Steiner tree and arborescence problems
- Linear matroid intersection is in quasi-NC
- Bipartite perfect matching is in quasi-NC
- Parameterized Algorithms for List K-Cycle
- Bipartite perfect matching in pseudo-deterministic NC
- Linear representation of transversal matroids and gammoids parameterized by rank
Cited In (8)
- A fast algorithm to construct a representation for transversal matroids
- The templates for some classes of quaternary matroids
- Efficient computation of representative sets with applications in parameterized and exact algorithms
- Linear representation of transversal matroids and gammoids parameterized by rank
- Vandermonde matrices, NP-completeness and transversal subspaces
- FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
- Linear representation of transversal matroids and gammoids parameterized by rank
- Finding temporal paths under waiting time constraints
Uses Software
This page was built for publication: Quasipolynomial representation of transversal matroids with applications in parameterized complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993296)
