Show simple item record

Consultant
dc.contributor.advisor
Alpár, Jüttner
Author
dc.contributor.author
Péter, Madarasi 
Availability Date
dc.date.accessioned
2018-05-16T07:37:13Z
Availability Date
dc.date.available
2018-05-16T07:37:13Z
Release
dc.date.issued
2017
uri
dc.identifier.uri
http://hdl.handle.net/10831/38081
Abstract
dc.description.abstract
This paper presents the concept of walk-labeling that can be used to decide the graph isomorphism problem in polynomial time combinatorially under certain conditions - which hold for a wide range of the graph pairs. It turns out that all non-cospectral graph pairs can be differentiated with a combinatorial method, furthermore, even if the graphs are cospectral and nonisomorphic, they might be distinguished by combinatorially verifying certain properties of their eigenspaces. Strong walk-labeling, a strengthening of the aforementioned labeling, has also been introduced for practical purposes. Its applications include speeding up any backtracking graph matching algorithm, and the generation of graph fingerprints, which identify all the graphs uniquely it was tested on, including all known strongly regular graphs. To practically evaluate the new methods, tests have been carried out on biological, strongly regular and random graph.hu_HU
Language
dc.language.iso
angolhu_HU
Title
dc.title
Counting Walks - a Novel Approach to the Graph Isomorphism Problemhu_HU
Language
dc.language.rfc3066
eng
Scope
dc.format.page
36hu_HU
Author
dc.contributor.inst
ELTE Természettudományi Kar Matematikai Intézethu_HU
Keywords
dc.subject.hu
mathematicshu_HU
Keywords
dc.subject.hu
Matematikus TDK
Keywords
dc.subject.hu
TDK dolgozat
Type
dc.type.type
hallgatói dolgozathu_HU
Release Date
dc.description.issuedate
2017hu_HU
Student's vocational, professional, specialization
dc.description.course
matematikushu_HU


Files in this item

Counting Walks - a Novel Approach to the Graph Isomorphism Problem
 

This item appears in the following Collection(s)

Show simple item record