View source for 18510754. Weighted Alternating Paths in Graphs for Quantum Computing simplified abstract (Google LLC)

=Weighted Alternating Paths in Graphs for Quantum Computing=


==Organization Name==

[[:Category:Google LLC|Google LLC]]


[[Category:Google LLC]]

==Inventor(s)==

[[:Category:Nathan Cody Jones of Los Angeles CA (US)|Nathan Cody Jones of Los Angeles CA (US)]][[Category:Nathan Cody Jones of Los Angeles CA (US)]]

==Weighted Alternating Paths in Graphs for Quantum Computing - A simplified explanation of the abstract==


This abstract first appeared for US patent application 18510754 titled 'Weighted Alternating Paths in Graphs for Quantum Computing

==Simplified Explanation==

The abstract describes a computer-implemented method for expanding a set of matched nodes in a partially-matched graph by finding an alternating path between two unmatched nodes and updating the matching label of the edges along this path.

* Obtaining a partially-matched graph with a matching set and one or more edges with matching labels.
* Obtaining at least two unmatched nodes.
* Determining an alternating path between the two unmatched nodes.
* Inverting the matching label of the edges along the alternating path to include the unmatched nodes in the matching set.

== Potential Applications ==
This technology could be applied in various fields such as network optimization, data analysis, and pattern recognition.

== Problems Solved ==
This technology helps in efficiently expanding matched nodes in a graph, which can be useful in improving graph matching algorithms and network analysis.

== Benefits ==
The method offers a systematic approach to expanding matched nodes in a partially-matched graph, leading to better graph matching results and enhanced graph analysis capabilities.

== Potential Commercial Applications ==
Potential commercial applications of this technology include graph database systems, social network analysis tools, and recommendation systems.

== Possible Prior Art ==
One possible prior art could be the use of alternating paths in graph theory for solving matching problems, but the specific method described in the patent application may be novel.

=== What are the specific steps involved in determining an alternating path in the method described? ===
The specific steps involved in determining an alternating path include identifying two unmatched nodes, finding a path between them that alternates between matched and unmatched edges, and updating the matching labels along this path.

=== How does inverting the matching label of an edge contribute to expanding the set of matched nodes in the graph? ===
Inverting the matching label of an edge allows for including the two unmatched nodes connected by this edge in the matching set, thereby expanding the set of matched nodes in the graph. This step ensures that the matching set grows while maintaining the matching constraints of the graph.


==Original Abstract Submitted==

A computer-implemented method for expanding a set of matched nodes in a partially-matched graph can include obtaining, by a computing system, a partially-matched graph having a matching set, the partially-matched graph including one or more edges and a plurality of nodes, the one or more edges having a matching label. The method can include obtaining at least two unmatched nodes. The method can include determining an alternating path from a first unmatched node of the at least two unmatched nodes to a second unmatched node of the at least two unmatched nodes, the alternating path including at least one edge of the one or more edges. The method can include inverting the matching label of the at least one edge of the alternating path such that the at least two unmatched nodes are included in the matching set of the partially-matched graph.



[[Category:G06F11/10]]
[[Category:G06F16/901]]
[[Category:G06N10/00]]