Muhammad Farhan

Buddhi Kothalawala, Henning Koehler, Muhammad Farhan

The Maximum Common Subgraph (MCS) problem plays a key role in many applications, including cheminformatics, bioinformatics, and pattern recognition, where it is used to identify the largest shared substructure between two graphs. Although symmetry exploitation is a powerful means of reducing search space in combinatorial optimization, its potential in MCS algorithms has remained largely underexplored due to the challenges of detecting and integrating symmetries effectively. Existing approaches, such as RRSplit, partially address symmetry through vertex-equivalence reasoning on the variable graph, but symmetries in the value graph remain unexploited. In this work, we introduce a complete dual-symmetry breaking framework that simultaneously handles symmetries in both variable and value graphs. Our method identifies and exploits modular symmetries based on local neighborhood structures, allowing the algorithm to prune isomorphic subtrees during search while rigorously preserving optimality. Extensive experiments on standard MCS benchmarks show that our approach substantially outperforms the state-of-the-art RRSplit algorithm, solving more instances with significant reductions in both computation time and search space. These results highlight the practical effectiveness of comprehensive symmetry-aware pruning for accelerating exact MCS computation.

Muhammad Farhan, Henning Koehler

Modern route planners such as Google Maps and Apple Maps serve millions of users worldwide, optmizing routes in large-scale road networks where fast responses are required under diverse cost metrics including travel time, fuel consumption, and toll costs. Classical algorithms like Dijkstra or A$^*$ are too slow at this scale, and while index-based techniques achieve fast queries, they are often tied to fixed metrics, making them unsuitable for dynamic conditions or user-specific metrics. Customizable approaches address this limitation by separating metric-independent preprocessing and metric-dependent customization, but they remain limited by slower query performance. Notably, Customizable Tree Labeling (CTL) was recently introduced as a promising framework that combines tree labelings with shortcut graphs. The shortcut graph enables efficient customization to different cost metrics, while tree labeling, supported by path arrays, provides fast query answering. Although CTL enables optimizing routes under different cost metrics, it still faces challenges in storing and reconstructing path information efficiently, which hinders its scalability for answering millions of queries. In this article, we build on the Customizable Tree Labeling framework to introduce new optimizations for the storage and reconstruction of path information. We develop several algorithmic variants that differ in the information retained within shortcut graphs and path arrays, offering a spectrum of trade-offs between memory usage and query performance. To further enhance scalability, we propose a batch processing strategy that shares path information across queries to eliminate redundant computation. Empirically, we have evaluated the performance of our algorithms on 13 real-world road networks. The results show that they significantly outperform state-of-the-art methods.

Aamir Khan, Muhammad Farhan, Asar Ali

With the advancement of communication and security technologies, it has become crucial to have robustness of embedded biometric systems. This paper presents the realization of such technologies which demands reliable and error-free biometric identity verification systems. High dimensional patterns are not permitted due to eigen-decomposition in high dimensional feature space and degeneration of scattering matrices in small size sample. Generalization, dimensionality reduction and maximizing the margins are controlled by minimizing weight vectors. Results show good pattern by multimodal biometric system proposed in this paper. This paper is aimed at investigating a biometric identity system using Support Vector Machines(SVMs) and Lindear Discriminant Analysis(LDA) with MFCCs and implementing such system in real-time using SignalWAVE.

Aamir Khan, Muhammad Farhan, Aasim Khurshid et al.

Essentially a biometric system is a pattern recognition system which recognizes a user by determining the authenticity of a specific anatomical or behavioral characteristic possessed by the user. With the ever increasing integration of computers and Internet into daily life style, it has become necessary to protect sensitive and personal data. This paper proposes a multimodal biometric system which incorporates more than one biometric trait to attain higher security and to handle failure to enroll situations for some users. This paper is aimed at investigating a multimodal biometric identity system using Linear Discriminant Analysis as backbone to both facial and speech recognition and implementing such system in real-time using SignalWAVE.