A weighted matroid intersection algorithm

DOI10.1016/0196-6774(81)90032-8zbMath0484.05025OpenAlexW2033329811WikidataQ56987216 ScholiaQ56987216MaRDI QIDQ3942972

András Frank

Publication date: 1981

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(81)90032-8

zbMATH Keywords

independent setprimal-dual algorithmmatroid polyhedral intersection theorem

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Algorithms in computer science (68W99)

Related Items

Minimum \(k\) arborescences with bandwidth constraints, Convexity and Steinitz's exchange property, Algorithms for the partial inverse matroid problem in which weights can only be increased, Matroid representation of clique complexes, Matroid bases with cardinality constraints on the intersection, Inverse matroid intersection problem, A cost-scaling algorithm for computing the degree of determinants, The popular matching and condensation problems under matroid constraints, Generalized polymatroids and submodular flows, A dual approximation approach to weighted matroid intersection, Bracing cubic grids - a necessary condition, Robustness of minimum cost arborescences, Shortest bibranchings and valuated matroid intersection, A bound for the symmetric travelling salesman problem through matroid formulation, Multi-objective matroid optimization with ordinal weights, A tour of \(M\)-part \(L\)-Sperner families, Popular Matchings with Ties and Matroid Constraints, The \(b\)-branching problem in digraphs, Two algorithms for weighted matroid intersection, A deterministic parallel reduction from weighted matroid intersection search to decision, On Fair Division under Heterogeneous Matroid Constraints, Covering directed graphs by in-trees, Matroid Intersection under Restricted Oracles, Covering Directed Graphs by In-Trees, Unnamed Item, Diverse collections in matroids and graphs, Relay placement for fault tolerance in wireless networks in higher dimensions, Lagrangean decomposition: A model yielding stronger lagrangean bounds, Recent Developments in Discrete Convex Analysis, Unnamed Item, On a weighted linear matroid intersection algorithm by deg-det computation, On finding optimal polytrees, Blocking optimal arborescences, Crashing a maximum-weight complementary basis, Steiner trees with \(n\) terminals among \(n+1\) nodes, Poset matching---a distributive analog of independent matching, An algorithm for optimum common root functions of two digraphs, Applications of combinatorics to statics --- a second survey, The complexity of finding arborescences in hypergraphs, Approximation algorithms for the Euclidean bipartite TSP, Optimal matroid partitioning problems, Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications, A detachment algorithm for inferring a graph from path frequency, The base-matroid and inverse combinatorial optimization problems., Rooted \(k\)-connections in digraphs, Pareto Stable Matchings under One-Sided Matroid Constraints, Exact and approximation algorithms for weighted matroid intersection, Unnamed Item, Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings, A multiply constrained matroid optimization problem, Persistency and matroid intersection, Fenchel-type duality for matroid valuations, Discrete convex analysis, A note on submodular set cover on matroids, The intersection of a matroid and a simplicial complex, Finding feasible vectors of Edmonds-Giles polyhedra, Approximate tradeoffs on weighted labeled matroids, Market Pricing for Matroid Rank Valuations, Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems, Minimum cost source location problem with vertex-connectivity requirements in digraphs