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

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

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

(9)

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

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)