The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
A Backtracking Algorithmic Toolbox for Solving the Subgraph Isomorphism Problem
|
|
Author(s): Jurij Mihelič (Faculty of Computer and Information Science, University of Ljubljana, Slovenia), Uroš Čibej (Faculty of Computer and Information Science, University of Ljubljana, Slovenia)and Luka Fürst (Faculty of Computer and Information Science, University of Ljubljana, Slovenia)
Copyright: 2021
Pages: 39
Source title:
Handbook of Research on Methodologies and Applications of Supercomputing
Source Author(s)/Editor(s): Veljko Milutinović (Indiana University, Bloomington, USA)and Miloš Kotlar (University of Belgrade, Serbia)
DOI: 10.4018/978-1-7998-7156-9.ch014
Purchase
|
Abstract
The subgraph isomorphism problem asks whether a given graph is a subgraph of another graph. It is one of the most general NP-complete problems since many other problems (e.g., Hamiltonian cycle, clique, independent set, etc.) have a natural reduction to subgraph isomorphism. Furthermore, there is a variety of practical applications where graph pattern matching is the core problem. Developing efficient algorithms and solvers for this problem thus enables good solutions to a variety of different practical problems. In this chapter, the authors present and experimentally explore various algorithmic refinements and code optimizations for improving the performance of subgraph isomorphism solvers. In particular, they focus on algorithms that are based on the backtracking approach and constraint satisfaction programming. They gather experiences from many state-of-the-art algorithms as well as from their engagement in this field. Lessons learned from engineering such a solver can be utilized in many other fields where backtracking is a prominent approach for solving a particular problem.
Related Content
|
Radhika Kavuri, Satya kiranmai Tadepalli.
© 2024.
19 pages.
|
|
Ramu Kuchipudi, Ramesh Babu Palamakula, T. Satyanarayana Murthy.
© 2024.
10 pages.
|
|
Nidhi Niraj Worah, Megharani Patil.
© 2024.
21 pages.
|
|
Vishal Goar, Nagendra Singh Yadav.
© 2024.
23 pages.
|
|
S. Boopathi.
© 2024.
24 pages.
|
|
Sai Samin Varma Pusapati.
© 2024.
25 pages.
|
|
Swapna Mudrakola, Krishna Keerthi Chennam, Shitharth Selvarajan.
© 2024.
11 pages.
|
|
|