Skip navigation
Skip navigation

Isomorphism of (mis)labeled graphs

Schweitzer, Pascal

Description

For similarity measures of labeled and unlabeled graphs, we study the complexity of the graph isomorphism problem for pairs of input graphs which are close with respect to the measure. More precisely, we show that for every fixed integer k we can decide in quadratic time whether a labeled graph G can be obtained from another labeled graph H by relabeling at most k vertices. We extend the algorithm solving this problem to an algorithm determining the number ℓ of vertices that must be deleted and...[Show more]

CollectionsANU Research Publications
Date published: 2011
Type: Conference paper
URI: http://hdl.handle.net/1885/59215
Source: Lecture Notes in Computer Science series
DOI: 10.1007/978-3-642-23719-5_32

Download

File Description SizeFormat Image
01_Schweitzer_Isomorphism_of_(mis)labeled_2011.pdf211.73 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator