What type of study is this?

This is a Quantitative Study study.

September 12, 2025Open Access

Achieving Polynomial Time Complexity in Maximum Common Subgraph (MCS) Computation with reference to Text Modeling

Key Points

The proposed method achieves polynomial time complexity, allowing for faster MCS computation.
It demonstrates improved efficiency over traditional methods in measuring similarity in graph representations.
This research successfully tackles a significant challenge in graph theory, paving the way for future advancements.
The findings were substantiated through an example illustrating the approach's effectiveness and efficiency.

Abstract

Objectives: To make representation of text through directed labeled graph and also to achieve Maximum Common Subgraph (MCS) computation in limited time for the purpose of measuring similarity among the graphical objects. Method: This work has employed the maximum common subgraph approach for measuring the similarity in between two objects under representation. Findings: The proposed approach is successful in achieving polynomial time complexity, which is theoretically established in this article. The new similarity measure so developed is also more effective and efficient than the prevailing method and is shown with the help of an arbitrary example. Novelty: Achieving polynomial time complexity for the maximum common subgraph problem is a significant challenge in graph theory and algorithm design. This research has demonstrated how polynomial time complexity can be achieved in case of maximum common subgraph computation problem with directed and completely labeled graph in a methodical way. Keywords: Time Complexity, Text Representation, Graph, MCS, Word Net

Read Full Paperexternally

AI에게 질문

Bookmark

View Full Paper