Computational complexity of simultaneous elementary matching problems

DOI10.1007/3-540-60246-1_142MaRDI QIDQ5900977zbMATH OpenOpenAlexFDO

Authors Miki Hermann, Phokion G. Kolaitis

Publication date 17 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60246-1_142

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mechanization of proofs and logical operations (03B35)

Recommendations

• Computational complexity of simultaneous elementary matching problems
• scientific article; zbMATH DE number 3921983
• Complexity of matching problems
• Simultaneous matchings: Hardness and approximation
• Certain NP-complete matching problems
• Computational complexity of existence problems for matchings in graphs.
• On the complexity of a family of generalized matching problems
• Parameterized complexity of perfectly matched sets
• On the computational complexity of the bipartizing matching problem
• scientific article; zbMATH DE number 1341609

Cited in

(7)

• Unification algorithms cannot be combined in polynomial time.
• Complexity of matching problems
• Unification algorithms cannot be combined in polynomial time
• The complexity of counting problems in equational matching
• Single elementary associative-commutative matching
• The Complexity of Rationalizing Matchings
• Some complexity theoretic aspects of AC rewriting

This page was built for publication: Computational complexity of simultaneous elementary matching problems

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