Efficient algorithms for a family of matroid intersection problems
From MaRDI portal
Publication:3335803
DOI10.1016/0196-6774(84)90042-7zbMath0545.05029MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05B35: Combinatorial aspects of matroids and geometric lattices
Related Items
Small degree out‐branchings, Bicolored matchings in some classes of graphs, Models, relaxations and exact approaches for the capacitated vehicle routing problem, Efficient algorithms for robustness in resource allocation and scheduling problems, Semi-preemptive routing on a linear and circular track, Probabilistic single processor scheduling, An algorithm for finding a matroid basis which maximizes the product of the weights of the elements, The 2-quasi-greedy algorithm for cardinality constrained matroid bases, 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, An augmenting path algorithm for linear matroid parity, On-line updating of solutions to a class of matroid intersection problems, Exact arborescences, matchings and cycles, 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, Color constrained combinatorial optimization problems, Steiner trees with \(n\) terminals among \(n+1\) nodes, An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem, Efficient associative algorithm to find the least spanning tree of a graph with a node degree constraint, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, The vertex degrees of minimum spanning trees, A multiply constrained matroid optimization problem, A data structure for dynamic trees, Matroid optimization with generalized constraints, An exact algorithm for the capacitated shortest spanning arborescence, Semi–preemptive routing on a line
