scientific article; zbMATH DE number 19225
From MaRDI portal
Publication:3976656
[For the entire collection see Zbl 0734.00014.] Let \(G=(V,E)\) be a finite undirected graph. A maximum matching is a maximum cardinality subset \(E_ 1\subseteq E\), s.t. all edges in \(E_ 1\) are pairwise independent, i.e. they are not incident to a common vertex. The problem of determining whether \(G\) contains \(k\) disjoint maximum matchings is \({\mathcal NP}\)-complete. A linear algorithm for solving the problems on trees is given.
Recommendations
- Matchability and \(k\)-maximal matchings
- Complexity of a disjoint matching problem on bipartite graphs
- On complexity of special maximum matchings constructing
- Parameterized and approximation algorithms for finding two disjoint matchings
- Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
- On k-match problems
- On minimum maximal distance-\(k\) matchings
- On minimum maximal distance-\(k\) matchings
- scientific article; zbMATH DE number 1303560
Cited in
(13)- Maximum bounded \(H\)-matching is Max SNP-complete
- Tutte sets in graphs. II: The complexity of finding maximum Tutte sets
- Recovery of disrupted airline operations using \(k\)-maximum matching in graphs
- Complexity of a disjoint matching problem on bipartite graphs
- Discontinuities in the complexities of some graph recognition problems
- Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
- scientific article; zbMATH DE number 1003276 (Why is no real title available?)
- scientific article; zbMATH DE number 4025482 (Why is no real title available?)
- Efficient algorithms for disjoint matchings among intervals and related problems
- Disconnected matchings
- Disconnected matchings
- Matchability and \(k\)-maximal matchings
- On complexity of special maximum matchings constructing
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976656)
