On complexity of special maximum matchings constructing
From MaRDI portal
Publication:952636
DOI10.1016/j.disc.2007.04.029zbMath1159.05319arXiv0707.2126OpenAlexW1635686141MaRDI QIDQ952636
R. R. Kamalian, Vahan V. Mkrtchyan
Publication date: 12 November 2008
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0707.2126
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (7)
Complexity of a disjoint matching problem on bipartite graphs ⋮ Unnamed Item ⋮ 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 ⋮ Supermodularity in Unweighted Graph Optimization I: Branchings and Matchings ⋮ Supermodularity in Unweighted Graph Optimization II: Matroidal Term Rank Augmentation ⋮ Blockers and transversals
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- The labeled perfect matching in bipartite graphs
- Matching theory
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- An NP-complete matching problem
- Some simplified NP-complete graph problems
- Induced matchings
- Parallel concepts in graph theory
- Coloured matchings in bipartite graphs
- Generalized subgraph-restricted matchings in graphs
- Complexity of a 3-dimensional assignment problem
- TWO THEOREMS IN GRAPH THEORY
- An Algorithm for a Minimum Cover of a Graph
- The NP-Completeness of Edge-Coloring
- The complexity of restricted spanning tree problems
- Some Matching Problems for Bipartite Graphs
- Paths, Trees, and Flowers
- Maximum matching and a polyhedron with 0,1-vertices
- Maximum matching in a convex bipartite graph
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Uniquely restricted matchings
This page was built for publication: On complexity of special maximum matchings constructing
