Random pseudo-polynomial algorithms for exact matroid problems

DOI10.1016/0196-6774(92)90018-8MaRDI QIDQ3990608zbMATH OpenOpenAlexFDO

Authors Giulia Galbiati, Francesco Maffioli, 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

zbMATH Keywords

perfect matchingsmatroidweighted graphspseudo-polynomial algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Recommendations

• Polymatroids: Construction and random algorithms
• Weighted linear matroid parity
• A weighted linear matroid parity algorithm
• A weighted linear matroid parity algorithm
• Exact and approximation algorithms for weighted matroid intersection

Cited in

(44)

• The Medusa algorithm for polynomial matings
• Exact matching: correct parity and FPT parameterized by independence number
• New approaches to multi-objective optimization
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Techniques for generalized colorful k-center problems
• Generalized center problems with outliers
• Algebraic algorithms for linear matroid parity problems
• A constant approximation for colorful k-center
• Exact arborescences, matchings and cycles
• Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid
• Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
• Budgeted colored matching problems
• Weighted linear matroid parity
• Advances on strictly \(\varDelta \)-modular IPs
• Recent results on approximating the Steiner tree problem and its generalizations
• Approximating bounded degree deletion via matroid matching
• Advances on strictly -modular IPs
• New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems
• A weighted linear matroid parity algorithm
• Algorithms for measuring perturbality in matroid optimization
• On the congruency-constrained matroid base
• Towards a polynomial-time randomized algorithm for closed product-form networks
• Solving NP-hard semirandom graph problems in polynomial expected time
• A simple PTAS for weighted matroid matching on strongly base orderable matroids
• The combinatorial approach yields an NC algorithm for computing Pfaffians
• A cost-scaling algorithm for computing the degree of determinants
• Weighted matching with pair restrictions
• Generalized center problems with outliers
• Polymatroids: Construction and random algorithms
• The image of weighted combinatorial problems
• Bounding the payment of approximate truthful mechanisms
• Problems on group-labeled matroid bases
• Lower bounds for matroid optimization problems with a linear constraint
• Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
• RNC-approximation algorithms for the steiner problem
• Pandora's box problem with time constraints
• Random pseudo-polynomial algorithms for some combinatorial programming problems
• On the exact matching problem in dense graphs
• On the difficulty of finding walks of length k
• Obtaining approximately optimal and diverse solutions via dispersion
• Combination algorithms for Steiner tree variants
• Randomized algorithms over finite fields for the exact parity base problem.
• A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with 2 2 submatrices
• On the computation of pfaffians

This page was built for publication: Random pseudo-polynomial algorithms for exact matroid problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3990608)