Partitioning to three matchings of given size is NP-complete for bipartite graphs

DOI10.1515/AUSI-2015-0004MaRDI QIDQ2254544zbMATH OpenOpenAlexFDO

Authors Dömötör Pálvölgyi

Publication date 5 February 2015

Published in Acta Universitatis Sapientiae. Informatica (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://doi.org/10.1515/ausi-2015-0004

zbMATH Keywords

bipartite graphsdisjoint matchingsNP-completenesspartitioning

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The path partition problem and related problems in bipartite graphs
• On complexity of special maximum matchings constructing
• Complexity of a disjoint matching problem on bipartite graphs
• Certain NP-complete matching problems
• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs

Cites work

• Some simplified NP-complete graph problems

Cited in

(18)

• On the sets of perfect matchings for two bipartite graphs
• Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
• Bipartizing with a matching
• The path partition problem and related problems in bipartite graphs
• Complexity of a disjoint matching problem on bipartite graphs
• Fair allocation of indivisible items with conflict graphs
• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
• On the NP-completeness of the perfect matching free subgraph problem
• Fair Packing of Independent Sets
• Supermodularity in unweighted graph optimization. I: Branchings and matchings
• Supermodularity in unweighted graph optimization. II: Matroidal term rank augmentation
• Triangle packing on tripartite graphs is hard
• Algorithms and Computation
• Maximizing edge-ratio is NP-complete
• Certain NP-complete matching problems
• Rectangular partition is polynomial in two dimensions but NP-complete in three
• Simultaneous matchings: Hardness and approximation
• On complexity of special maximum matchings constructing

This page was built for publication: Partitioning to three matchings of given size is NP-complete for bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2254544)