Deterministic Truncation of Linear Matroids
From MaRDI portal
Publication:3448849
DOI10.1007/978-3-662-47672-7_75zbMath1440.68127arXiv1404.4506OpenAlexW2793135015MaRDI QIDQ3448849
Fahad Panolan, Saket Saurabh, Pranabendu Misra, Daniel Lokshtanov
Publication date: 27 October 2015
Published in: ACM Transactions on Algorithms, Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.4506
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorial aspects of matroids and geometric lattices (05B35) Randomized algorithms (68W20)
Related Items (21)
Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Deterministic parameterized algorithms for the graph motif problem ⋮ Parameterized counting of trees, forests and matroid bases ⋮ Simultaneous feedback edge set: a parameterized perspective ⋮ Finding even subgraphs even faster ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Unnamed Item ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ On the Complexity of Recovering Incidence Matrices ⋮ Finding temporal paths under waiting time constraints ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Unnamed Item ⋮ Representative families for matroid intersections, with applications to location, packing, and covering problems ⋮ Complexity of packing common bases in matroids ⋮ Linear representation of transversal matroids and gammoids parameterized by rank ⋮ Parameterized complexity of conflict-free set cover ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Generalized matroid matching ⋮ Editing to Connected F-Degree Graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of connected even/odd subgraph problems
- A parameterized view on matroid optimization problems
- Wronskians and linear independence in fields of prime characteristic
- An extremal problem for two families of sets
- Deterministic extraction from weak random sources.
- Deterministic extractors for affine sources over large fields
- Explicit subspace designs
- Parameterized complexity of Eulerian deletion problems
- Representative Sets of Product Families
- Representative Families: A Unified Tradeoff-Based Approach
- Wronskians and Linear Independence
- Extensions of Lipschitz mappings into a Hilbert space
- Powers of tensors and fast matrix multiplication
- Algebraic Functions and Projective Curves
- An elementary proof of a theorem of Johnson and Lindenstrauss
- Representative Sets and Irrelevant Vertices
- Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Finding Even Subgraphs Even Faster
- Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- On identity testing of tensors, low-rank recovery and compressed sensing
- Multiplying matrices faster than coppersmith-winograd
- On generalized graphs
- Long Circuits and Large Euler Subgraphs
- Matrices and matroids for systems analysis
This page was built for publication: Deterministic Truncation of Linear Matroids
