Algorithms for finding k-best perfect matchings
From MaRDI portal
Publication:1090343
DOI10.1016/0166-218X(87)90017-5zbMath0621.05026MaRDI QIDQ1090343
Chandra R. Chegireddy, Horst W. Hamacher
Publication date: 1987
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach, Algorithms for finding a \(K\)th best valued assignment, Exact solution approaches for bilevel assignment problems, A decision-theoretic approach to robust optimization in multivalued graphs, A note on \(K\) best network flows, An efficient procedure for finding best compromise solutions to the multi-objective assignment problem, k-Best constrained bases of a matroid, Choquet-based optimisation in multiobjective shortest path and spanning tree problems, An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set, k-optimal solution sets for some polynomially solvable scheduling problems, Heuristic enhancements of the search for the generation of all perfect matchings, Polynomial-delay and polynomial-space enumeration of large maximal matchings, A fuzzy model for NMT word alignment using quasi-perfect matching, A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives, Two phase algorithms for the bi-objective assignment problem, Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search, An algorithm for ranking assignments using reoptimization, Unnamed Item, Adjacency on combinatorial polyhedra, Adjacency of the best and second best valued solutions in combinatorial optimization problems, Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph, Finding all the perfect matchings in bipartite graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Algorithm 562: Shortest Path Lengths [H]
- Sensitivity analysis of optimal matchings
- A shortest augmenting path method for solving minimal perfect matching problems
- Shortest alternating path algorithms
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Paths, Trees, and Flowers
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- A Dual Shortest Path Algorithm
