Implementation of a Subgraph Matching Algorithm - Graphmatcher

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Suomela, Jukka Ünlü, Emre 2017-12-18T11:48:07Z 2017-12-18T11:48:07Z 2017-12-11
dc.description.abstract As graph databases and using graph as a data structure attract more and more interest of the industry, inevitably research towards to graphs is also accelerated by this interest. Significant amount of effort has been dedicated to graph theory related research by IT industry giants such as Google and IBM with Cayley or Facebook with GraphQL. In the domain of graph theory, Subgraph Matching is one of the basic graph problems which has always room for an improvement. Therefore, numerous methods and algorithms have been developed to produce better results for different class of input graphs, such as Ullmann's Algorithm, VF2, GraphQL, TurboISO and DualISO. In this work, I have attempted to solve a subgraph matching problem encountered in a task scheduling system for software development processes. In the same vein, problem that I was attempting to solve also touched to a scheduling problem known as Job Shop Problem. To solve both problems efficiently at one time, I have developed our subgraph matching method, Graphmatcher. It is essentially a fork of DualISO algorithm with additional functionality towards efficient solution of scheduling problems I have encountered. In the practical part of this thesis, I have given detailed information about design and implementation of Graphmatcher and task scheduler application. Also I have explained how does Graphmatcher add value into task scheduling application and what kind of effect does it make under different conditions. To prove efficiency of our method, I have written tests which use various combinations of parameters and made observations from production environment. Based on results, I claim that our method of Graphmatcher is able to solve similar problems with ease and add value into software development processes by utilizing more resources at once. en
dc.format.extent 48+5
dc.language.iso en en
dc.title Implementation of a Subgraph Matching Algorithm - Graphmatcher en
dc.type G2 Pro gradu, diplomityö fi Sähkötekniikan korkeakoulu fi
dc.subject.keyword algorithms fi
dc.subject.keyword subgraph isomorphism fi
dc.subject.keyword graph pattern matching fi
dc.subject.keyword job shop scheduling problem fi
dc.subject.keyword optimization fi
dc.identifier.urn URN:NBN:fi:aalto-201712187968
dc.programme.major Communications Engineering en
dc.programme.mcode ELEC3029 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Suomela, Jukka
dc.programme CCIS - Master’s Programme in Computer, Communication and Information Sciences (TS2013) en
dc.ethesisid Aalto 9705
dc.location P1 fi

Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication