Efficient algorithms for a family of matroid intersection problems
From MaRDI portal
Publication:3335803
DOI10.1016/0196-6774(84)90042-7zbMath0545.05029OpenAlexW2036940456MaRDI QIDQ3335803
Harold N. Gabow, Robert Endre Tarjan
Publication date: 1984
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(84)90042-7
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35)
Related Items
Efficient algorithms for robustness in resource allocation and scheduling problems, The 2-quasi-greedy algorithm for cardinality constrained matroid bases, On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\), Eine Min-Max Beziehung für das Exakte Matroid Problem. (A min-max relation for the exact matroid problem), Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Semi-preemptive routing on a linear and circular track, An augmenting path algorithm for linear matroid parity, On-line updating of solutions to a class of matroid intersection problems, Optimization problems with color-induced budget constraints, Exact arborescences, matchings and cycles, Small degree out‐branchings, Improved algorithms for joint optimization of facility locations and network connections, Matroid optimization with generalized constraints, An exact algorithm for the capacitated shortest spanning arborescence, A matroid algorithm and its application to the efficient solution of two optimization problems on graphs, A Lagrangean approach to the degree-constrained minimum spanning tree problem, Preference profiles determining the proposals in the Gale-Shapley algorithm for stable matching problems, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Multi-objective matroid optimization with ordinal weights, Min‐sum controllable risk problems with concave risk functions of the same value range, An extension of the Christofides heuristic for a single-depot multiple Hamiltonian path problem, Biobjective optimization problems on matroids with binary costs, An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint, Probabilistic single processor scheduling, Generalized multiple objective bottleneck problems, Approximating the least core value and least core of cooperative games with supermodular costs, A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees, Color constrained combinatorial optimization problems, On the generality of the greedy algorithm for solving matroid base problems, Bicolored matchings in some classes of graphs, Steiner trees with \(n\) terminals among \(n+1\) nodes, An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem, Preprocessing and cut generation techniques for multi-objective binary programming, Models, relaxations and exact approaches for the capacitated vehicle routing problem, Efficient solution of the matroid product problem, A multiply constrained matroid optimization problem, Optimization Problems with Color-Induced Budget Constraints, Efficient associative algorithm to find the least spanning tree of a graph with a node degree constraint, A data structure for dynamic trees, The vertex degrees of minimum spanning trees, Semi–preemptive routing on a line, An algorithm for finding a matroid basis which maximizes the product of the weights of the elements
