Quantum algorithms for matching problems

DOI10.1007/S00224-008-9118-XMaRDI QIDQ839634zbMATHOpenAlexFDO

Authors Sebastian Dörn

Publication date 2 September 2009

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-008-9118-x

zbMATH Keywords

graph theoryquantum algorithmsmatching problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Quantum Algorithms for Matching and Network Flows
• Efficient algorithms for finding maximum matching in graphs
• Quantum algorithms for the triangle problem
• Quantum search of matching on signed graphs
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1270594 (Why is no real title available?)
• A decomposition theorem for maximum weight bipartite matchings
• Algorithms – ESA 2004
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Automata, Languages and Programming
• Automata, Languages and Programming
• Automata, Languages and Programming
• Faster Scaling Algorithms for Network Problems
• Graph theory with applications
• Quantum Algorithms for Element Distinctness
• Quantum Algorithms for Matching and Network Flows
• Quantum algorithms for the triangle problem
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Quantum verification of matrix products
• SOFSEM 2004: Theory and Practice of Computer Science
• The Quantum Query Complexity of Algebraic Properties

Cited in

(10)

• Phase matching in Grover's algorithm
• A Correspondence Measure for Graph Matching Using the Discrete Quantum Walk
• Quantum algorithm for dynamic programming approach for DAGs and applications
• A query-efficient quantum algorithm for maximum matching on general graphs
• Quantum search of matching on signed graphs
• A bounded-error quantum polynomial-time algorithm for two graph bisection problems
• Quantum Algorithms for Matching and Network Flows
• scientific article; zbMATH DE number 6667586 (Why is no real title available?)
• Quantum algorithm for shortest path search in directed acyclic graph
• Quantum search for the dating market

This page was built for publication: Quantum algorithms for matching problems

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