Matroid Intersection under Restricted Oracles

DOI10.1137/22m152579xzbMath1519.90201arXiv2209.14516MaRDI QIDQ6161263

Tamás Király, Yu Yokoi, Yutaro Yamaguchi, Kristóf Bérczi

Publication date: 27 June 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2209.14516

zbMATH Keywords

tractabilitymatroid intersectioncommon independence oraclemaximum rank oraclerank sum oracle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rooted \(k\)-connections in digraphs
• Matroid matching and some applications
• The dependence graph for bases in matroids
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Independence and port oracles for matroids, with an application to computational learning theory
• Hypergraph characterization of split matroids
• Exact and approximation algorithms for weighted matroid intersection
• Matroids from hypersimplex splits
• Matroid Intersection
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Two algorithms for weighted matroid intersection
• The computational complexity of matroid properties
• Algorithmic versus axiomatic definitions of matroids
• Complexity of Matroid Property Algorithms
• A weighted matroid intersection algorithm
• Matroid intersection algorithms
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Comments on bases in dependence structures
• Matching Theory for Combinatorial Geometries

This page was built for publication: Matroid Intersection under Restricted Oracles