go-v.orgdoi

Intersection of Two Matroids: (Condensed) Border Graphs and Ranking

Paolo M. Camerini, Horst W. Hamacher · SIAM Journal on Discrete Mathematics · 1989

  • DOI 10.1137/0402002
  • Publisher Society for Industrial and Applied Mathematics
  • Type article
  • Issued 1989

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

SIAM Journal on Discrete Mathematics · Society for Industrial and Applied Mathematics · article · 1989

Abstract

Given two matroids $M_1 = (E,\mathcal{J}_1 )$ and, $M_2 = (E,\mathcal{J}_2 )$, three algorithms for finding K best intersections $I_1 ,I_2 , \cdots ,I_K $ are presented. The first version is a straightforward application of a general procedure due to Murty and Lawler. The complexity for finding $I_2 , \cdots ,I_k $ is $O(Km^2 R(R + c(m) + \log m))$ where m is the number of elements in $E, R = \min \{ r_1 (E),r_2 (E)\} $, and $c(m)$ is the complexity of an independence oracle. By using maximum weighted border paths to compute second best intersections of modified matroids, this bound is reduced to $O(K(m^3 + mRc(m))$.

Finally, a condensed version of the border graph is proposed to further improve the bound to $O(KmRc(m))$. The latter idea can also be used to find the optimal intersection $I_1 $ in $O(mR^2 c(m))$ time, which is competitive with recent matroid intersection algorithms by Frank [J. Algorithms, 2 (1981), pp. 328–336] and Brezovec, Cornuejols, and Glover [Math. Programming, 36 (1986), pp. 39–53].

Open the resolved locator · 10.1137/0402002

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 08:34 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1137/0402002
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.