Complexity of packing common bases in matroids
From MaRDI portal
Publication:2039228
DOI10.1007/s10107-020-01497-yzbMath1467.05024arXiv1903.03579OpenAlexW3015204455MaRDI QIDQ2039228
Kristóf Bérczi, Tamás Schwarcz
Publication date: 2 July 2021
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.03579
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35)
Related Items
Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids, On the complexity of packing rainbow spanning trees, Partitioning into common independent sets via relaxing strongly base orderability, Diverse collections in matroids and graphs, Rainbow Odd Cycles, On the impossibility of decomposing binary matroids
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the number of matroids compared to the number of sparse paving matroids
- A parameterized view on matroid optimization problems
- Directed cut transversal packing for source-sink connected graphs
- On packing connectors
- On the relations of various conjectures on Latin squares and straightening coefficients
- Minimal edge-coverings of pairs of sets
- Independence and port oracles for matroids, with an application to computational learning theory
- The \(b\)-branching problem in digraphs
- On the asymptotic proportion of connected matroids
- Excluded \(t\)-factors in bipartite graphs: a unified framework for nonbipartite matchings and restricted 2-matchings
- A note on disjoint dijoins
- On reachability mixed arborescence packing
- A generalized-polymatroid approach to disjoint common independent sets in two matroids
- On partitioning two matroids into common independent subsets
- Note on a min-max conjecture of Woodall
- On Disjoint Common Bases in Two Matroids
- Lattice Theory of Generalized Partitions
- Deterministic Truncation of Linear Matroids
- On Rota's Basis Conjecture
- The computational complexity of matroid properties
- Algorithmic versus axiomatic definitions of matroids
- Complexity of Matroid Property Algorithms
- Min-max Relations for Directed Graphs
- Rigidity Matroids
- Disjoint Common Transversals and Exchange Structures
- A Catalogue of Combinatorial Geometries
- Reduction of Rota's Basis Conjecture to a Problem on Three Bases
- The complexity of satisfiability problems
- Rota’s Basis Conjecture for Paving Matroids
- Transversals and matroid partition
- Lectures on matroids
- On the Vector Representations of Induced Matroids
- Term Rewriting and Applications
- Halfway to Rota’s Basis Conjecture
- Derandomizing polynomial identity tests means proving circuit lower bounds
