On complexity of special maximum matchings constructing

DOI10.1016/J.DISC.2007.04.029zbMATH Open1159.05319arXiv0707.2126OpenAlexW1635686141MaRDI QIDQ952636FDOQ952636

Authors: R. R. Kamalian, Vahan V. Mkrtchyan 

Publication date: 12 November 2008

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0707.2126

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

zbMATH Keywords

bipartite graphmaximum matching\(NP\)-completeness

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matching theory
• Paths, Trees, and Flowers
• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• Maximum matching and a polyhedron with 0,1-vertices
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Some simplified NP-complete graph problems
• Title not available (Why is that?)
• The labeled perfect matching in bipartite graphs
• Induced matchings
• Parallel concepts in graph theory
• TWO THEOREMS IN GRAPH THEORY
• Some Matching Problems for Bipartite Graphs
• Title not available (Why is that?)
• Complexity of a 3-dimensional assignment problem
• Maximum matching in a convex bipartite graph
• An Algorithm for a Minimum Cover of a Graph
• The complexity of restricted spanning tree problems
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Uniquely restricted matchings
• Generalized subgraph-restricted matchings in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Coloured matchings in bipartite graphs
• An NP-complete matching problem

Cited In (16)

• On the sets of perfect matchings for two bipartite graphs
• Characterization of a class of graphs related to pairs of disjoint matchings
• On the NP-completeness of the perfect matching free subgraph problem
• Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation
• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
• Blockers and transversals
• The complexity of matching with bonds
• Title not available (Why is that?)
• Computational complexity of existence problems for matchings in graphs.
• Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings
• Complexity of a disjoint matching problem on bipartite graphs
• Title not available (Why is that?)
• On upper bounds for parameters related to the construction of special maximum matchings
• Maximum matching of given weight in complete and complete bipartite graphs
• Title not available (Why is that?)
• DNA computing of bipartite graphs for maximum matching

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)