Algorithms for finding k-best perfect matchings
From MaRDI portal
In the K-best perfect matching problem (KM) one wants to find K pairwise different, perfect matchings \(M_ 1,...,M_ k\) such that \(w(M_ 1)\geq w(M_ 2)\geq...\geq w(M_ k)\geq w(M)\), \(\forall M\neq M_ 1,M_ 2,...,M_ k\). The procedure discussed in this paper is based on a binary partitioning of the matching solution space. We survey different algorithms to perform this partitioning. The best complexity bound of the resulting algorithms discussed is \(O(Kn^ 3)\), where n is the number of nodes in the graph.
Recommendations
Cites work
- A Dual Shortest Path Algorithm
- A note on two problems in connexion with graphs
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- A shortest augmenting path method for solving minimal perfect matching problems
- Algorithm 562: Shortest Path Lengths [H]
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3637616 (Why is no real title available?)
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- Paths, Trees, and Flowers
- Sensitivity analysis of optimal matchings
- Shortest alternating path algorithms
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Cited in
(29)- k-optimal solution sets for some polynomially solvable scheduling problems
- Adjacency of the best and second best valued solutions in combinatorial optimization problems
- Finding all the perfect matchings in bipartite graphs
- Algorithms for finding a \(K\)th best valued assignment
- Adjacency on combinatorial polyhedra
- Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach
- A note on \(K\) best network flows
- Heuristic enhancements of the search for the generation of all perfect matchings
- Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
- A decision-theoretic approach to robust optimization in multivalued graphs
- Two phase algorithms for the bi-objective assignment problem
- An algorithm for ranking assignments using reoptimization
- Choquet-based optimisation in multiobjective shortest path and spanning tree problems
- Exact solution approaches for bilevel assignment problems
- Extended Kuhn-Munkres algorithm for constrained matching search
- An efficient procedure for finding best compromise solutions to the multi-objective assignment problem
- k-Best constrained bases of a matroid
- scientific article; zbMATH DE number 176477 (Why is no real title available?)
- A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives
- scientific article; zbMATH DE number 6863589 (Why is no real title available?)
- \(k\)-best solutions of MSO problems on tree-decomposable graphs
- scientific article; zbMATH DE number 4197736 (Why is no real title available?)
- An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
- Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
- Polynomial-delay and polynomial-space enumeration of large maximal matchings
- A fuzzy model for NMT word alignment using quasi-perfect matching
- A complexity map of probabilistic reasoning for neurosymbolic classification techniques
- Learning equilibria in matching markets with bandit feedback
- On finding -th smallest perfect matchings
This page was built for publication: Algorithms for finding k-best perfect matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1090343)
