Random pseudo-polynomial algorithms for exact matroid problems
From MaRDI portal
Publication:3990608
DOI10.1016/0196-6774(92)90018-8zbMath0773.05032OpenAlexW1988698339MaRDI QIDQ3990608
Francesco Maffioli, Giulia Galbiati, Paolo M. Camerini
Publication date: 28 June 1992
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(92)90018-8
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Combinatorial aspects of matroids and geometric lattices (05B35)
Related Items
On the computation of pfaffians ⋮ Approximating Bounded Degree Deletion via Matroid Matching ⋮ The combinatorial approach yields an NC algorithm for computing Pfaffians ⋮ RNC-approximation algorithms for the steiner problem ⋮ Random parallel algorithms for finding exact branchings, perfect matchings, and cycles ⋮ New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems ⋮ A cost-scaling algorithm for computing the degree of determinants ⋮ New approaches to multi-objective optimization ⋮ Advances on strictly \(\varDelta \)-modular IPs ⋮ Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle ⋮ Obtaining approximately optimal and diverse solutions via dispersion ⋮ A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices ⋮ Unnamed Item ⋮ Combination algorithms for Steiner tree variants ⋮ A simple PTAS for weighted matroid matching on strongly base orderable matroids ⋮ Bounding the payment of approximate truthful mechanisms ⋮ Polymatroids: Construction and random algorithms ⋮ The image of weighted combinatorial problems ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ Budgeted colored matching problems ⋮ Random pseudo-polynomial algorithms for some combinatorial programming problems ⋮ Weighted matching with pair restrictions ⋮ On the difficulty of finding walks of length k ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ Unnamed Item ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ Generalized Center Problems with Outliers ⋮ Recent results on approximating the Steiner tree problem and its generalizations ⋮ Unnamed Item ⋮ Randomized algorithms over finite fields for the exact parity base problem.
This page was built for publication: Random pseudo-polynomial algorithms for exact matroid problems
