Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
This office action is in response to submission of application on 5/22/2023.
Claims 1-8 are presented for examination.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 3 and 7 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 3 recites “…which as…” , which is structurally incoherent in the context of the claim step. It appears the applicant intended to recite “which has”.
Claim 7 recites “…when not tree line…”. This lacks grammatical syntax and renders the conditional logic of the step unclear. It appears the applicant intended to recite “when no tree line”.
Claim 3 recites “the first start site”, which lacks proper antecedent basis. Claim 1 and claim 2 introduce only “a start site”. Be reciting “the first start site,” the claim introduces an ambiguous distinction that leaves it unclear whether it refers back to the previously introduced “start site” or is attempting to introduce a new, separate element without an initial indefinite article.
Claim 7 recites “the first start site” twice and lacks proper antecedent basis. Claim 5 introduced only “a start site”. Be reciting “the first start site,” the claim introduces an ambiguous distinction that leaves it unclear whether it refers back to the previously introduced “start site” or is attempting to introduce a new, separate element without an initial indefinite article.
Claim 7 further recites “the first start site”, which lacks proper antecedent basis. Claim 5 introduces only “a start site.” Because no “first start site” has been previously introduced or defined in the claim chain, the scope of the limitation is unclear. It cannot be determined whether “the first start site” is intended to refer back to the “a start site” of Claim 5 or if it is attempting to introduce a new, separate element without the required initial indefinite article (“a” or “an).
Appropriate correction is required.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-8 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Independent Claims
Step 2A Prong One: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
Yes, independent claim 1 recites an abstract idea in the form of mental processes. A mental process is a process that “can be performed in the human mind, or by a human using a pen and paper” (MPEP§ 2106.04(a)(2)(III), paragraph 1). Examples of mental processes include “observations, evaluations, judgments, and opinions” (MPEP § 2106.04(a)(2)(III), paragraph 2).
The following limitations of claim 1 are mental processes:
a step of recognizing three or more sites within a designated area of a target and setting a start site among the recognized sites; [This is a mental process that can be performed by observations, evaluations, judgments, and opinions. No specific methodology for recognizing and setting a site is recited in the claim; therefore, it broadly encompasses processing that can be performed as a mental process.]
a step of extracting a tree graph by connecting sites within the designated area, starting with the start site; [This is a mental process that can be performed by observations, evaluations, judgments, and opinions. No specific methodology for connecting sites with an area is recited in the claim; therefore, it broadly encompasses processing that can be performed as a mental process.]
a step of extracting the shortest path between sites within the designated area of the target by connecting tree lines of the tree graph, starting with the start site; [This is a mental process that can be performed by observations, evaluations, judgments, and opinions. No specific methodology for connecting tree lines of a tree graph is recited in the claim; therefore, it broadly encompasses processing that can be performed as a mental process.]
Therefore, the independent claims recite a judicial exception.
Step 2A Prong Two: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No. The judicial exception recited in the above discussed claims is not integrated into a practical application. There are no more additional elements.
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No. The claims do not include additional elements that are sufficient for the claims to
amount to significantly more than the judicial exception. There are no more additional elements.
Independent claim 5 recites the same relevant limitations and a similar analysis
applies. Claim 5 recites the additional elements of "extracting device comprising: a processor comprising instructions implementing an algorithm for extracting the shortest path between sites within a target" - a device consisting of a processor and an algorithm are components recited at a high level are construed as generic computer components and algorithms used to implement the abstract idea. See MPEP 2106.05(f)(2). As such, the limitations do not integrate the abstract idea into a practical application. Nor to do they amount to significantly more.
Therefore, the independent claims are not patent eligible.
Dependent Claims
The remaining dependent claims being rejected do not recite additional elements, whether considered individually or in combination, that are sufficient to integrate the judicial exception into a practical application or amount to significantly more than the judicial exception.
Claims 2 and 6
“a first tree line generating step of searching a first site located at the shortest distance from the start site and connecting the first site with the start site, and generating a first tree line including the start site and the first site” [This further limitation is also a mental process, as a human mind can search a site located at the shortest distance from a site, and then connect and generate a tree line between them. This claim does not recite any additional non-abstract elements for purposes of Step 2A Prong Two and Step 2B analysis]
“a second tree line generating step of searching a second site located at the shortest distance from the first tree line and connecting the second site with the first tree line, and generating a second tree line including the first tree line and the second site” [This further limitation is also a mental process, as a human mind can search a site located at the shortest distance from a tree line, and then connect and generate a tree line between them. This claim does not recite any additional non-abstract elements for purposes of Step 2A Prong Two and Step 2B analysis]
“a non-regression tree graph extracting step of extracting a tree graph without regression within the designated area by repeating the steps until all sites within the designated area are connected” [This further limitation is also a mental process, as a human mind can search a site located at the shortest distance from a tree line, and then connect and generate a tree line between them and repeat within an area until all sites are connected. This claim does not recite any additional non-abstract elements for purposes of Step 2A Prong Two and Step 2B analysis]
Claims 3 and 7
“a step of connecting a third tree line having the lowest site index among tree lines connected with the first start site with the first start site” [This further limitation is also a mental process, as a human mind can select a tree line with the lowest site index and connect it to a site. This claim does not recite any additional non-abstract elements for purposes of Step 2A Prong Two and Step 2B analysis]
“a step of connecting a fourth tree line, which has the lowest site index among tree lines connected with the third tree line, with the third tree line” [This further limitation is also a mental process, as a human mind can select a tree line with the lowest site index and connect it to a site. This claim does not recite any additional non-abstract elements for purposes of Step 2A Prong Two and Step 2B analysis]
“a step of connecting a fifth tree line, which as the lowest site index among tree lines not connected with the fourth tree line after recurring to the previous site, with the fourth tree line, when no tree line is connected with the fourth tree line” [This further limitation is also a mental process, as a human mind can select a tree line with the lowest site index and connect it to a site. This claim does not recite any additional non-abstract elements for purposes of Step 2A Prong Two and Step 2B analysis]
Claim 7 recites the additional elements of “extracts the shortest path for all sites within a designated area of a target by repeating the above-processes until passing all sites within a designated area of a target” [This further limitation is also a mental process, as a human mind can select a tree line with the lowest site index and connect it to a tree line and repeat within an area until all sites are passed. This claim does not recite any additional non-abstract elements for purposes of Step 2A Prong Two and Step 2B analysis]
Claims 4 and 8
“the step of setting the start site sets one of sites recognized within the designated area of the target as the start site based on an input setting signal” [This further limitation is also a mental process, as a human mind can set a site based on a signal. This claim does not recite any additional non-abstract elements for purposes of Step 2A Prong Two and Step 2B analysis]
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1-2, 4-6, and 8 are rejected under 35 U.S.C. 102(a)(l) as being anticipated by US6356911B1 to Shibuya et al. (hereinafter Shibuya).
Per claim 1, Shibuya discloses A target-based shortest path extracting method comprising [column 1, line 6 “The invention relates to a shortest path search system, and in particular to a method and a system for searching for the shortest path between multiple nodes.”.]:
a step of recognizing three or more sites within a designated area of a target [Related Art, column 1, line 10 “The problem of finding the shortest path between multiple nodes is a problem for which a set of a plurality of sources and a set of a plurality of destinations are provided, and the shortest source-destination path is found for each source paired with each of the destinations in the set of destinations.”. (note: this explicitly operates on a plurality of nodes (sites) within a graph (designated area of a target). The set of a plurality of sources and a set of a plurality of destinations is the three or more sites that must be recognized. The nodes collectively define the designated search area.; column 4 “for (all nodes v) path p(v) = +∞;”. (note: the algorithm initializes all nodes in the graph, which is recognizing all sites within the designated area. Every node in the designated area is identified and stored before path computation begins.)] and
setting a start site among the recognized sites [column 3, line 54 “At Step 300, a shortest path established set S is initialized, and the first node s is entered in a priority queue (Priority Oueue). The maximum value is entered in advance as path lengths p(v) for all nodes v, which are the sources of the paths. The first path length p(s) is 0.”. (note: this designates a first node s as the starting point of the algorithm, which is setting a start site. The start node s is entered into the priority queue first, with a path length of 0, marking it as the origin of the path search); column 4, line 40 “Enter source s in priority queue. path p(s) = 0;”. (note: the source node s is the start site set among all recognized nodes)]; a step of extracting a tree graph by connecting sites within the designated area, starting with the start site [column 3, line 54 “At Step 300, a shortest path established set S is initialized, and the first node S is entered in a priority queue (Priority Oueue).”; column 3, line 64 “at step 330 a node v is searched for in the priority queue that has the smallest p(v)+h(V) value.”; column 2, line 34 “each node w is specified at which a path length p(w) is equal to or greater than the sum of a path length p(v) between the source and node V and a path length between node V and the specified node w.”. (note: Shibuya builds a connected graph of shortest paths starting from source node s, progressively connecting additional nodes (sites) by finding the neareast node w to the already-connected set. This process, starting from s and iteratively connecting additional nodes, is extracting a tree graph by connecting sites within the designated area, starting with the start site)]; and
a step of extracting the shortest path between sites within the designated area of the target by connecting tree lines of the tree graph, starting with the start site [column 4, line 16 “At step 350, node v is added to the established set S, and at step 360 a check is performed to determine whether the destination set T is included in the set S.”; column 2, line 32 “When all the destinations are stored, the shortest path search is terminated.”; column 1, line 32 “Delete, from priority queue, node v having smallest path p(v) value. Enter v in established set S. if (established set S includes destination set T) break.”. (note: after building the connected set S (tree graph), it extracts the shortest path by confirming all destination nodes are included and determining the path via the established connections)].
Per claim 2, Shibuya discloses claim 1, further disclosing a first tree line generating step of searching a first site located at the shortest distance from the start site and connecting the first site with the start site, and generating a first tree line including the start site and the first site [column 3, line 64 “at step 330 a node v is searched for in the priority queue that has the smallest p(v)+h(V) value.”; column 3, line 54 “At Step 300, a shortest path established set S is initialized, and the first node s is entered in a priority queue (Priority Oueue). The maximum value is entered in advance as path lengths p(v) for all nodes v, which are the sources of the paths. The first path length p(s) is 0.”; column 1, line 32 “Delete, from priority queue, node v having smallest path p(v) value. Enter v in established set S.”. (note: after initializing from start node s (start site) with p(s)=0, the algorithm immediately finds the node v with the smallest path length from s, which is the first site located at the shortest distance from the start site. Adding node v to the established set S and recording the edge s to v, is generating the first tree line including the start site and the first site )]; a second tree line generating step of searching a second site located at the shortest distance from the first tree line and connecting the second site with the first tree line, and generating a second tree line including the first tree line and the second site [column 2, line 34 “each node w is specified at which a path length p(w) is equal to or greater than the sum of a path length p(v) between the source and node V and a path length between node V and the specified node w.”; column 4, line 47 “for (all edges e (destinations w) having v as a source) { if (p(w) > p(v) + edge length (e)) {p(w) = (p(v) + edge length (e); Enter w in priority queue.}}”. (note: after the first tree line is generated, s to v, the algorithm searches for al nodes w adjacent to the established tree, finds the one with the smallest combined path length (shortest distance from the first tree line), and adds it with a new edge. This edge is the second tree line including the first tree line and the second site. The shortest distance from the first tree line is the shortest distance from any node already in the tree, which is what the priority queue computes.)]; and
a non-regression tree graph extracting step of extracting a tree graph without regression within the designated area by repeating the steps until all sites within the designated area are connected [column 4, line 16 “…a check is performed to determine whether the destination set T is included in the set S.”; column 2, line 32 “When all the destinations are stored, the shortest path search is terminated.”; column 1, line 32 “Delete, from priority queue, node v having smallest path p(v) value. Enter v in established set S. if (established set S includes destination set T) break.”. (note: Shibuya repeats the node-finding and tree-building process until all destination nodes (all sites) are included in the established set S. This loop continues until all sites within the designated area are connected, which is the non-regression tree graph extracting step. Without regression is part of the algorithm because each node is added to the established set S only once and the priority queue structure prevents revisiting.)].
Per claim 4, Shibuya discloses claim 1, further disclosing wherein the step of setting the start site sets one of sites recognized within the designated area of the target as the start site based on an input setting signal [column 3, line 54 “At Step 300, a shortest path established set S is initialized, and the first node S is entered in a priority queue (Priority Oueue).”; column 1, line 25 “1xNshortestPaths (sources, destination set T)”; column 3, line 20 “…user interface hardware, has a pointing device (a mouse or a joystick) 7 or a keyboard 6 for data input”. (note: the algorithm takes the sourcenode s as an explicit input parameter to te function, this is the input setting signal that deignates s as the start site. The source s is one of the recognized nodes (sites) in the graph (designated area). Setting p(s)=0 establishes s as the start, based on the input parameter. The system hardware described provides the way for receiving the input setting signal from a user.)].
Claim 5 is substantially similar in scope and spirit to claim 1. Therefore, the rejection of claim 1 is applied accordingly. Shibuya further shows the method being implemented by an apparatus [column 1, line 6 “The invention relates to a shortest path search system, and in particular to a method and a system for searching for the shortest path between multiple nodes.”.]
Claim 6 is substantially similar in scope and spirit to claim 2. Therefore, the rejection of claim 2 is applied accordingly. Shibuya further shows the method being implemented by an apparatus [Shibuya, column 1, line 6 “The invention relates to a shortest path search system, and in particular to a method and a system for searching for the shortest path between multiple nodes.”.]
Claim 8 is substantially similar in scope and spirit to claim 4. Therefore, the rejection of claim 4 is applied accordingly. Shibuya further shows the method being implemented by an apparatus [Shibuya, column 1, line 6 “The invention relates to a shortest path search system, and in particular to a method and a system for searching for the shortest path between multiple nodes.”].
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 3 and 7 are rejected under 35 U.S.C. 103 as being unpatentable over Shibuya in view of Introduction to Algorithms to Cormen et al. (hereinafter Cormen).
Per claim 3, Shibuya discloses claim 2.
Shibuya does not fully disclose, but with Cormen does teach: a step of connecting a third tree line having the lowest site index among tree lines connected with the first start site with the first start site [Cormen, pg. 603 “Depth-first search explores edges out of the most recently discovered vertex v that still has unexplored edges leaving it.”; pg. 604 “DFS(G)… for each vertex u ∈ G.V… if u: color == WHITE… DFS-VISIT(G, u)…Procedure DFS works as follows” (note: DFS traversal of the spanning tree starting from the root (start site) selects the first unvisited adjacent vertex. When neighbors are processed in ascending index order, Carmen processes neighbors in the order they appear in the adjacency list, which can be ordered by index, the algorithm selects the tree line with the lowest site index connected to the start site. This is connecting a third tree line having the lowest site index among tree lines connected with the first start site.)][Shibuya, column 5, line 50 “First, at step 400 a shortest path established set W is initialized, and set T of destinations is stored in a priority queue 2 (Priority Queue2) ...At step 470, the node v having the smallest p(v)+h(v) value is deleted from the priority queue.”. (note: the node finder function when applied to tree traversal after minimum spanning tree construction selects the connected node with the minimum index (lowest path cost), which is the tree line having the lowest site index. The priority queue orders nodes by their indices and selects the minimum first)];
a step of connecting a fourth tree line, which has the lowest site index among tree lines connected with the third tree line, with the third tree line [Cormen, pg. 603 “Depth-first search explores edges out of the most recently discovered vertex v that still has unexplored edges leaving it.”; pg. 604 “for each vertex u ∈ G.V… if u: color == WHITE… DFS-VISIT(G, u)” (note: after traversing the third tree line, reaching a new node, DFS immediately examines the unvisited neighbors of that new node and selects the one with the lowest index. This recursive descent of going from the node reached via the third tree line to its lowest -indexed child is connecting a fourth tree line, which has the lowest site index among tree lines connected with the third tree line.)]; and
a step of connecting a fifth tree line, which as the lowest site index among tree lines not connected with the fourth tree line after recurring to the previous site, with the fourth tree line, when no tree line is connected with the fourth tree line [Cormen, pg. 603 “Once all of v’s edges have been explored, the search “backtracks” to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex.”. (note: when the current node, the endpoint of the fourth tree line, has no unvisited tree line (when no tree line is connected with the fourth tree line), DFS backtracks to the previous node (recurring to the previous site) and selects the next lowest-indexed unvisited tree line from there (the fifth tree line. The has the lowest site index among tree lines not connected with the fourth tree line).)][Shibuya, column 4, line 42 “while (priority queue is not empty) {Delete, from priority queue, node v having smallest path p(v) value. Enter v in established set S. if (established set S destination set T) break.”. (note: the algorithm continues iterating, returning to previously stored nodes when a node has no further unexplored neighbors (empty neighbors in the current iteration), and selecting the next minimum cost node from the priority queue. When this is applied to tree traversal, it is recurring to the previous site) and connecting the next available tree line (fifth tree line.)]
Shibuya and Cormen are analogous art because they are from the same field of endeavor of graph-theoretic shortest path algorithms and spanning tree methods for routing between multiple nodes in a network.
Before the effective filing date of the claimed invention, it would have been obvious to a person of ordinary skill in the art to, after building the spanning tree, apply DFS traversal with index-ordered neighbor selection to the resulting tree as taught by Cormen.
The suggestion/motivation for doing so would have been because DFS guarantees visiting every node exactly once and index-ordered DFS is a standard trivial variant. This is explicitly stated by Cormen [pg. 603, “The strategy followed by depth-first search is, as its name implies, to search “deeper” in the graph whenever possible. Depth-first search explores edges out of the most recently discovered vertex that still has unexplored edges leaving it. Once all of ’s edges have been explored, the search “backtracks” to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex.”].
Per claim 7, Shibuya discloses claim 6.
Shibuya does not fully disclose, but with Cormen does teach: the processor connects a third tree line, which has the lowest site index among tree lines connected with the first start site, with the first start site, [Cormen, pg. 603 “Depth-first search explores edges out of the most recently discovered vertex v that still has unexplored edges leaving it.”; pg. 604 “DFS(G)… for each vertex u ∈ G.V… if u: color == WHITE… DFS-VISIT(G, u)…Procedure DFS works as follows” (note: DFS traversal of the spanning tree starting from the root (start site) selects the first unvisited adjacent vertex. When neighbors are processed in ascending index order, Carmen processes neighbors in the order they appear in the adjacency list, which can be ordered by index, the algorithm selects the tree line with the lowest site index connected to the start site. This is connecting a third tree line having the lowest site index among tree lines connected with the first start site.)][Shibuya, column 5, line 50 “First, at step 400 a shortest path established set W is initialized, and set T of destinations is stored in a priority queue 2 (Priority Queue2) ...At step 470, the node v having the smallest p(v)+h(v) value is deleted from the priority queue.”. (note: the node finder function when applied to tree traversal after minimum spanning tree construction selects the connected node with the minimum index (lowest path cost), which is the tree line having the lowest site index. The priority queue orders nodes by their indices and selects the minimum first)];
connects a fourth tree line, which has the lowest site index among tree lines connected with the third tree line, with the first start site [Cormen, pg. 603 “Depth-first search explores edges out of the most recently discovered vertex v that still has unexplored edges leaving it.”; pg. 604 “for each vertex u ∈ G.V… if u: color == WHITE… DFS-VISIT(G, u)” (note: after traversing the third tree line, reaching a new node, DFS immediately examines the unvisited neighbors of that new node and selects the one with the lowest index. This recursive descent of going from the node reached via the third tree line to its lowest -indexed child is connecting a fourth tree line, which has the lowest site index among tree lines connected with the third tree line.)],
connects a fifth tree line, which has the lowest site index among tree lines not connected after recurring to the previous site, with the fourth tree line when not tree line is connected with the fourth tree line [Cormen, pg. 603 “Once all of v’s edges have been explored, the search “backtracks” to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex.”. (note: when the current node, the endpoint of the fourth tree line, has no unvisited tree line (when no tree line is connected with the fourth tree line), DFS backtracks to the previous node (recurring to the previous site) and selects the next lowest-indexed unvisited tree line from there (the fifth tree line. The has the lowest site index among tree lines not connected with the fourth tree line).)][Shibuya, column 4, line 42 “while (priority queue is not empty) {Delete, from priority queue, node v having smallest path p(v) value. Enter v in established set S. if (established set S destination set T) break.”. (note: the algorithm continues iterating, returning to previously stored nodes when a node has no further unexplored neighbors (empty neighbors in the current iteration), and selecting the next minimum cost node from the priority queue. When this is applied to tree traversal, it is recurring to the previous site) and connecting the next available tree line (fifth tree line.)], and
extracts the shortest path for all sites within a designated area of a target by repeating the above-processes until passing all sites within a designated area of a target [Cormen, pg. 603 “This process continues until we have discovered all the vertices that are reachable from the original source vertex.”; pg. 604 “for each vertex u ∈ G.V… if u: color == WHITE… DFS-VISIT(G, u).”. (note: DFS continues repeating the traversal and backtracking processes until all vertices (all sites within the designated area) have been visited (color != WHITE). Then, the complete DFS traversal path is made of the shortest path for all sites, as the DFS tree path through a spanning tree is the unique path from the start to every other vertex.)][Shibuya, column 4, line 16 “At step 350, node v is added to the established set S, and at step 360 a check is performed to determine whether the destination set T is included in the set S.”; column 2, line 32 “When all the destinations are stored, the shortest path search is terminated.”. (note: the search processes repeat until all sites are included (until passing all sites within a designated area of a target). It terminates when all the destinations are stored.)]. Shibuya and Cormen are analogous art because they are from the same field of endeavor of graph-theoretic shortest path algorithms and spanning tree methods for routing between multiple nodes in a network.
Before the effective filing date of the claimed invention, it would have been obvious to a person of ordinary skill in the art to, after building the spanning tree, apply DFS traversal with index-ordered neighbor selection to the resulting tree as taught by Cormen.
The suggestion/motivation for doing so would have been because DFS guarantees visiting every node exactly once and index-ordered DFS is a standard trivial variant. This is explicitly stated by Cormen [pg. 603, “The strategy followed by depth-first search is, as its name implies, to search “deeper” in the graph whenever possible. Depth-first search explores edges out of the most recently discovered vertex that still has unexplored edges leaving it. Once all of ’s edges have been explored, the search “backtracks” to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex.”].
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Patents and/or related publications are cited in the Notice of References Cited (Form PTO-892) attached to this action to further show the state of the art with respect to network traversal and graph-extraction methodologies.
Salowe discloses the data architecture for generating a Minimum Spanning Tree layout, which is the foundation for the path extraction and backtracking algorithms.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Sayed M Shah whose telephone number is (571)272-9406. The examiner can normally be reached Monday-Friday 5:30 am - 1:30 pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Miranda Huang can be reached at (571) 270-7092. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/SAYED MUNEER SHAH/Examiner, Art Unit 2124
/MIRANDA M HUANG/ Supervisory Patent Examiner, Art Unit 2124
Prosecution Insights