Graph matching problems and the NP-hardness of sortedness constraints

DOI10.1016/J.TCS.2017.07.019MaRDI QIDQ2402671zbMATH OpenOpenAlexFDO

Authors Irena Rusu

Publication date 13 September 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2017.07.019

zbMATH Keywords

bipartite graphcomputational complexityconstraint programminggraph matchingsortedness constraints

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) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 2084708
• A constrained matching problem
• Characterising tractable constraints
• On the completeness of a generalized matching problem
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1953189 (Why is no real title available?)
• scientific article; zbMATH DE number 2080315 (Why is no real title available?)
• Induced matchings
• Matching theory
• Maximum weight edge-constrained matchings
• On maximum induced matchings in bipartite graphs
• On Representatives of Subsets
• On some matching problems arising in vehicle scheduling models
• Some Matching Problems for Bipartite Graphs
• The labeled perfect matching in bipartite graphs

Cited in

(3)

• On the hardness of solving edge matching puzzles as SAT or CSP problems
• \(\mathcal{IV}\)-matching is strongly \textsf{NP}-hard
• scientific article; zbMATH DE number 3965452 (Why is no real title available?)

Describes a project that uses

Uses Software

• Gecode
• SICStus
• MiniZinc

This page was built for publication: Graph matching problems and the NP-hardness of sortedness constraints

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