首页>
外国专利>
METHOD AND SYSTEM FOR IDENTIFICATION OF ISOMORPHS FOR GENERALISED JOHNSON GRAPHS IN POLYNOMIAL TIME
METHOD AND SYSTEM FOR IDENTIFICATION OF ISOMORPHS FOR GENERALISED JOHNSON GRAPHS IN POLYNOMIAL TIME
展开▼
机译:多项式时间内广义约翰逊图的同质异质性鉴定方法和系统
展开▼
页面导航
摘要
著录项
相似文献
摘要
The present disclosure is related to method and system for deducung the isomorphic graphs for a query graph from among a graph dataset of Generalised Johnson graphs, in polynomial time. A root device may create queries for determination of isomorphism for a Generalised Johnson graph, wherein a query graph G(V, E) (where, V is the set of vertices in the graph �G�� and E is the set of corresponding edges); may have a bijective function for one-to-one and onto mapping with the member of graph dataset H(W, F) (where, W is the set of vertices in the graph �H�� and F is the set of corresponding edges). The existing embodiments perform this function in non-deterministic polynomial time. These methods are time consuming and the complexity of task increases exponentially with respect to the size of vertex set. Hence, there exists a need for a method and system to reduce the time and operational complexity of Generalised Johnson graph isomorphism determination to polynomial time. The time complexity related disadvantages in the existing methods are overcome and substantial advantages presented through the present disclosure as implemented in the current embodiment. Two graphs would be classified as isomorphic and correspondence between their respective vertex sets identified provided both follow identical structure.
展开▼