On complexity of special maximum matchings constructing
From MaRDI portal
Publication:952636
Abstract: For bipartite graphs the NP-completeness is proved for the problem of existence of maximum matching which removal leads to a graph with given lower(upper)bound for the cardinality of its maximum matching.
Recommendations
- Computational complexity of existence problems for matchings in graphs.
- On upper bounds for parameters related to the construction of special maximum matchings
- scientific article; zbMATH DE number 19225
- Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
- Partitioning to three matchings of given size is NP-complete for bipartite graphs
Cites work
- scientific article; zbMATH DE number 177817 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1194938 (Why is no real title available?)
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- scientific article; zbMATH DE number 3231693 (Why is no real title available?)
- scientific article; zbMATH DE number 3060538 (Why is no real title available?)
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An Algorithm for a Minimum Cover of a Graph
- An NP-complete matching problem
- Coloured matchings in bipartite graphs
- Complexity of a 3-dimensional assignment problem
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- Generalized subgraph-restricted matchings in graphs
- Induced matchings
- Matching theory
- Maximum matching and a polyhedron with 0,1-vertices
- Maximum matching in a convex bipartite graph
- Parallel concepts in graph theory
- Paths, Trees, and Flowers
- Some Matching Problems for Bipartite Graphs
- Some simplified NP-complete graph problems
- TWO THEOREMS IN GRAPH THEORY
- The NP-Completeness of Edge-Coloring
- The complexity of restricted spanning tree problems
- The labeled perfect matching in bipartite graphs
- Uniquely restricted matchings
Cited in
(19)- Maximum matching of given weight in complete and complete bipartite graphs
- Symmetric interdiction for matching problems
- Complexity of a disjoint matching problem on bipartite graphs
- Blockers and transversals
- scientific article; zbMATH DE number 19225 (Why is no real title available?)
- On the sets of perfect matchings for two bipartite graphs
- On the NP-completeness of the perfect matching free subgraph problem
- Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
- The minimum maximal k-partial-matching problem
- scientific article; zbMATH DE number 1953189 (Why is no real title available?)
- Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
- Computational complexity of existence problems for matchings in graphs.
- The complexity of matching with bonds
- Partitioning to three matchings of given size is NP-complete for bipartite graphs
- On upper bounds for parameters related to the construction of special maximum matchings
- Characterization of a class of graphs related to pairs of disjoint matchings
- DNA computing of bipartite graphs for maximum matching
- Supermodularity in unweighted graph optimization. I: Branchings and matchings
- Supermodularity in unweighted graph optimization. II: Matroidal term rank augmentation
This page was built for publication: On complexity of special maximum matchings constructing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q952636)
